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?
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!