Use binary search on the minimal edge weight:
Assume your search interval is [m, M]
. For a set value L = (m + M) / 2
, use BFS or DFS to find a path from source
to destination
such that all edges have weight >= L
. If you can do this, set m = L + 1
and repeat the search. If you cannot do this, set M = L - 1
and repeat the search.
This will be O((edges + nodes) log maxEdgeWeight)
. Should be very fast for your small number of nodes.
Note that there is a way to do it without the log factor as well, by using the ideas of Dijkstra's algorithm and counting sort. But you definitely do not need this for so few nodes.
Update 1:
Here is how this would work on your example. First of all, your search interval will be [2, 9000]
, since these are your min and max edge weights, respectively.
L = (2 + 9000) / 2 = 4501
=> Find a path from 1 to 8 such that all of its edges have weight >= 4501.
This is not possible, so reduce the search interval to [2, 4500].
L = (2 + 4501) / 2 = 2251
=> Find a path from 1 to 8 such that all of its edges have weight >= 2251.
This is not possible, reduce the search interval to [2, 2250]
L = (2 + 2250) / 2 = 1126
=> Not possible to find a path, reduce to [2, 1125]
L = (2 + 1125) / 2 = 563
=> Not possible, reduce to [2, 562]
L = (2 + 562) / 2 = 282
=> Success! We can find 1 -> 3 -> 5 -> 6 -> 7 -> 8
Mark 282 as the current best answer, and keep searching in [283, 562].
Eventually, you will be left with 283
as the answer, which is what you want. Then just print any path with all edge weights >= 283
(only one in your case).