Question

In Dijkstra's Algorithm, we compute path length to find the shortest path. The regular version of Dijkstra's Algorithm computes path length as sum of weights upto some node v. What if the path length is computed as sum of the lengths upto v + maximum weight traversed upto v ?

I have worked out on paper and found that it still works. But how do I prove it?

Help will be much appreciated

Était-ce utile?

La solution

If by "still works", you mean it results in the same shortest paths, here's a counter-example:

B --1-- C -- 1 -- D  
|                 |  
1                 1
|                 |  
S --3-- A ----1----   

Using just path length, the shortest path from S to A, will be via the edge from S to A. Using path length + max weight, the shortest path will be S to B to C to D to A, (weight 5). S to A will be weight 6.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top