Proving a modification in Dijkstra's Algorithm [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question appears to be off-topic because it lacks sufficient information to diagnose the problem. Describe your problem in more detail or include a minimal example in the question itself.

Closed 8 years ago.

Improve this 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

Answer 1

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.