CODEWITHSUNDEEP
javagraph-theorydijkstrajgraphtweighted-graph
Lake
Lake

Reputation: 4092

Graph minimum weight path

I have a weighted graph. I want to find the best path from node S to node E, so that the maximum single edge weight that was inside that path is the smallest possible.

For example:

S -> E (w=40)
S -> A (w=30)
A -> E (w=20)

For this graph, djikstra would calculate the shortest path to be S->E with cost 40. What I want instead, is S->A->E (with cost max(30, 20) = 30).

Is it possible to modify dijkstra in such a way? Or is there any known algorithm that accomplishes this?

Upvotes: 0

Views: 996

Answers (2)

bstadt
bstadt

Reputation: 146

You could use a Greedy Algorithm Variant:

1)Remove all edges, and sort edges with min first.

2)Add edges to the graph, in order from min to max, until there is a path from your source node to your target node. That path is the path you are looking for.

Upvotes: 0

MathBunny
MathBunny

Reputation: 956

The way you would solve this problem is changing the way you would store the distance (comparative value) from the priority queue / heap, but otherwise the structure would remain similar to Dijkstra's. You would store the maximum weight so far in the constructed path instead of the overall distance. This way, in your priority queue you would go in order for the smallest ones first.

So in the example you gave, It would start with S -> A because that has a w of 30, while the other one is 40. In the second execution, it would go to w = 20, with A -> E because Math.max(20, 30) is < 40, so it would be stored before in the priority queue / heap.

Once you get to the destination, then that path would be guaranteed to be the least. Hope this makes sense!

Upvotes: 1

Related Questions