GATE CSE 2020 | Question: 40

Question

Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $w(u,v)+f(u)-f(v)$.

Which one of the options completes the following sentence so that it is TRUE?

“The shortest paths in $G$ under $w$ are shortest paths under ${w}'$ too,_____________”.

• A. for every $f: V \rightarrow \mathbb{R}$
• B. if and only if $\forall u \in V, \: f(u)$ is positive
• C. if and only if $\forall u \in V, \: f(u)$ is negative
• D. if and only if $f(u)$ is the distance from $s$ to $u$ in the graph obtained by adding a new vertex $s$ to $G$ and edges of zero weight from $s$ to every vertex of $G$

Comments

Didn't find any of the explanations usefuI,all the explanations are next to useless.I couldn't even understand the question itself, spent more than 5 hrs on this.

Please check this video to understand what the problem  is and why does it work:-

https://youtu.be/DNRTlqPKK08

---

Thanks a lot bro 🫡

---

Good Explanation  (referecne yotube video )

https://gateoverflow.in/333191/gate-cse-2020-question-40?show=407710#a407710

Answer 1

Correct Answer: A

For any mapping of vertices to real values, the shortest paths won't change. All intermediate nodes values get canceled on any path you take and what you're left with is only the source and destination node values which would add up to cost on any path. Hence, the shortest paths would still be the same.

PS: Option D is wrong because of the "if and only if" clause in it. If it were "if", it would be correct. The condition given is sufficient but not necessary. Hence, "only if" is incorrect in the option. Basically it is saying $f(u)$ would be 0 for all vertices since they're connected to a new vertex s with zero weighted edge. Similarly options B and C are also wrong for the same reason.

Comments

@Abhrajyoti00

The way NEW Edge Weights are defined, for any path $Y$ from source $s$ to destination $d$ in $G$, the new length will become:

$\text{Old Length} + f(s) - f(d).$ So, the NEW length of any path ONLY depends on the source and the destination node of the path, NOT on any intermediate vertices on the path(intermediate vertices $f(v)$ values will cancel out, Only source’s $f(s)$ and destination’s $f(d)$ will remain).

For any two vertices $s,d;$ assume that we have two paths $P,Q$ from $s$ to $d.$ 

Assume in the Old Graph, Length of $P = P_{OLD}$ and Length of $Q = Q_{OLD} $ and assume that $P_{OLD} \leq Q_{OLD}.$

In the NEW Graph, Length of $P = P_{NEW} = P_{OLD} + f(s) – f(d)$ and

Length of $Q = Q_{NEW} = Q_{OLD} + f(s) – f(d).$

NOW, Since $P_{OLD} \leq Q_{OLD},$ So, WHATEVER real values $f(s),f(d) $ have, we have $P_{NEW} \leq Q_{NEW}.$

So, this statement is Correct: For any mapping of vertices to real values, the shortest paths won't change BUT length of Shortest path will definitely change(by a value $f(s) – f(d)$).

---

@Deepak Poonia Sir, thank you so much. It’s all clear now.

Regarding confusion between Option A and D, Sir can we say that : “For all functions it becomes true. But we don't require to add any new vertex 'S'. Although adding ‘S’ does not make it wrong”. Hence A is absolutely correct. But Option D is correct only one way and not the other. So iff is wrong making option D wrong.

 

---

@Abhrajyoti00

It doesn’t matter what is $f(u)$ for any $u.$ So, WHATEVER option is created regarding $f$ value of vertices, it will be only sufficient condition. Only option $A$ is necessary condition.

Just a small “Irrelevant to the question” note that Option $D$ is Not necessarily making all $f(u) = 0.$ In case of negative weights, for some vertices $f$ can be negative in option D. BUT again WHATEVER $f$ we have, it doesn’t matter.

Compiled my input on this question here:

https://gateoverflow.in/333191/gate-cse-2020-question-40?show=390945#a390945 

Answer 2

The way NEW Edge Weights are defined, for any path $Y$ from source $s$ to destination $d$ in $G$, the new length will become:

$\text{Old Length} + f(s) - f(d).$ So, the NEW length of any path ONLY depends on the source and the destination node of the path, NOT on any intermediate vertices on the path(intermediate vertices $f(v)$ values will cancel out, Only source’s $f(s)$ and destination’s $f(d)$ will remain).

For any two vertices $s,d;$ assume that we have two paths $P,Q$ from $s$ to $d.$ 

Assume in the Old Graph, Length of $P = P_{OLD}$ and Length of $Q = Q_{OLD} $ and assume that $P_{OLD} \leq Q_{OLD}.$

In the NEW Graph, Length of $P = P_{NEW} = P_{OLD} + f(s) – f(d)$ and

Length of $Q = Q_{NEW} = Q_{OLD} + f(s) – f(d).$

NOW, Since $P_{OLD} \leq Q_{OLD},$ So, WHATEVER real values $f(s),f(d) $ have, we have $P_{NEW} \leq Q_{NEW}.$

So, this statement is Correct: For any mapping of vertices to real values, the shortest paths won't change BUT length of Shortest path will definitely change(by a value $f(s) – f(d)$).

---

Regarding Option $D:$

It doesn’t matter what is $f(u)$ for any $u.$ So, WHATEVER option is created regarding $f$ value of vertices, it will be only sufficient condition. Only option $A$ is necessary & sufficient condition.

Just a small “Irrelevant to the question” note that Option $D$ is Not necessarily making all $f(u) = 0.$ In case of negative weights, for some vertices $f$ can be negative in option D. BUT again WHATEVER $f$ we have, it doesn’t matter.

Comments

@Deepak Poonia sir i am not able to understand last para. How “In case of negative weights, for some vertices f can be negative in option D”? As f(u) is the distance from s to u and edges weight are 0 that are connected from new vertex s to every other vertex in the graph so it means f(u) is 0 for all vertices 

---

@Shukla_, Note that in the graph $G,$ edge weights can be any real numbers. So, edge weights could be negative as well.

Now, in Option D, for any vertex $u,$ $f(u)$ is the distance from $s$ to $u$ which can be negative because in the original graph $G,$ edge weights could be negative. 

Answer 3

Ans-(a)

1. Given, We have a Graph G(V,E) and weight has real value.
2. Now, suppose we compute weight of edges in a new way such that between vertex u and v weight will be defiened as  wi +      f(u) - f(v). 'f' represent effective cost value at vertex u or v. 
3. Now if we want to find minimum cost path between vertex g and h. Then earlier it would have been all weights of edge in

    between g and h path summed. And then choose minimum among them. Assume those weights are w1 , w2  and w3. 

                                               
4. Now in new definition. We will get all edge weight computed. But we notice that all for computing minimum weight path

     we always have = $\sum$wi + f(g) - f(h). Rest all terms of 'f(x)' gets cancelled. If we choose another path then earlier we get

     value at part $\sum$wi different . But part f(g) - f(h) remains same always.

    So we have no change in shortest path under the new definition of edge weight too.

Comments

Assume we have to find shortest path between g and a. Then let w1,w2 be shortest path. Now for w1 new calculated weight will be w1+g-a and for w2 it will be w2+a-b. Now adding both we get w1+w2+g-b .

---

then according to question , "The shortest paths in G under w are shortest paths under w′ too", how is it possible?

Answer 4

Hi,

w(u,v) = (u, v) edge weight

w' (u,v) = w(u,v) + f(u) - f(v) = w( u,v)

Here f(u) - f(v) should be 0 .

So, option d is correct.