#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

Read the question carefully, there written distinct positive edge weights

---

I updated the image

---

@Kumar Ashish if you consider a graph with 3 vertices then you'll get the same edges in both the graphs! Please check.

---

@Kumar Ashish Also, please tell this one also - 

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then is it TRUE or FALSE?

Shortest path between any pair of vertices does not change?

---

if graph with 3 vertices is A,B,C and given AB = 3, BC=4 and AC=6. Initially, shortest path A->C =6. Now decrease edge weight by 2 for every one. AB=1, BC=2 and AC=4. So again, the shortest path changed as A->B->C = 3 instead of A->C .

---

It will be false even if you try to increase with the same value. suppose ABC is graph. AB=3 and BC=4 and AC=8. Shortest path from A to C = AB->BC = 7 but if you increase every edge by 2, AB=5, BC=6 and AC = 10, so shortest path from A to C = AC = 10.

Instead of checking my example, try to understand why this is happening. For this graph, since there are more than one edge in the shortest path(suppose n edges), increase every edge by k will increase that path weight by k+k+k..(n times) = n*k. whereas, a longer path which only had 1 edge or some small amount of edges(say m, where m<n), it will only be increase by m*k. For large enough value of k we can always get a new path.

---

@Kumar Ashish

Bhai, few questions - 

1) Why we always find the shortest path between the vertices who has the maximum weight edge present?

As you said - suppose ABC is graph. AB=3 and BC=4 and AC=8 then why can't we find the shortest path between BC. In all the examples you took and everyone else takes in this question is they find the shortest path only b/w the vertices which as MAX edge.

2) In case of increasing the edge weight one thing I've also noticed that " Jo maximum edge weight hai uska weight baki sab edges ke weights ke sum se zada hai tabhi answer False aata hai.

Ex as you took AB=3 and BC=4 and AC=8

Sabsa bada edge hai AC = 8

Baki dono remaining edges ka weight AB+BC < AC

==================================================================================

Agar mein aisa kar do AB = 4 BC = 7 and AC = 10 

Abhi sabsa bada edge toh AC = 10 hai , but AB + BC > AC and abhi agar graph banayo toh answer true aata hai jaise ke - 

shortest path b/w A to C is AC = 10 

abhi weight increase kardo 2 se. toh AB = 6 BC = 9 and AC = 11

Toh naye graph mein abhi bhi shortest path AC = 11 he raha kyunki 9+6 = 15 hoga. Toh abhi Yeh TRUE ho Gaya. 

Bhai mein bahut preshan hun kaisa graph lena hai, abhi exam mein kaise pata chalega ke edge weights kaise lene hai? Please help karen!

---

In case of increasing edge weights answer  tabhi FALSE aayega when - 

sum of all other edge weights < Max edge weights 

=================================================================

Aur in case of decreasing weights answer thabhi false hoga 

sum of all other edge weights > Max edge weights 

---

@ankitgupta.1729 Can you please pitch in?

---

@Kumar Ashish Ashish Sir, no answer?

---

Yes, you are right and I want you to understand the reason for this. Suppose there is a graph A,B,C,D,E. 

A->B=3

B->C=4

C->E=5

Path length A,B,C,E = 12 .

also, A->D=6 and D->E=7

Path length A,D,E = 13

Here, the shortest path from A to E would be A,B,C,E = 12.

Now, if we try to increase each weight by some constant k.

A->B=3+k, B->C=4+k, C->E=5+k and therefore, path length A,B,C,E = 12+3*k (please notice here that 3*k is being added to the overall path length)

also, A->D=6+k and D->E=7+k, therefore path length A,D,E = 13+2*k(again, notice here that 2*k is being added to the overall path length)

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

$13+2*k < 12+3*k$ .

If we can find such a value of k then the shortest path will definitely change. Here, for k=2, the shortest path will change to A,D,E and I want you to understand that it was because on the right hand side, even though the initial weight was 12, 3*k was being added to it which is greater than the 2*k on the left hand side. It means even if A,D,E path length was 5000 and A,B,C,D path length was just 12, it would still be possible to change the path length by adding some constant(which is going to be $k \geq 4989$ in this case).

Thus, it is important for you to understand that we are able to change the path length by increasing every edge by a constant amount because no. of edges on the smaller path is greater than the no. of edges in the greater path.

Similarly, in case of decreasing every edge by a constant amount, the path length will change if the no. of edges in the  greater path is more than the no. of edges in the smaller path. Please, try to think about this by taking more examples. This is the best way I could have explained it.

---

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!