#Algorithms MST Question Doubt

Question

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is decreased by the same value (constraint is - keeping all edge positive all the time), then is it TRUE or FALSE?

Shortest path between any pair of vertices does not change?

Answer 1

Shortest path between any pair of vertices may change.

Consider the following graph A,B,C,D 

Current shortest path between A and D is from A to D, which is 11 but if we reduce every edge weight by 2, the shortest path between A and D will be A->B->C->D which will be (1+2+3) = 6. 

Comments

Thank you so much Ashish, Sir for all your effort, time and patience and you explained it beautifully. 

Just one thing in this line - 

Now, for the new shortest path from A to E to become A,D,E, 

13+2*k > 12+3*k.

Shouldn't the sign be < as you put k=2 and can see, right?

---

Yes, thank you for pointing that out. I corrected it.

---

It's all good and thank you for everything!