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

So what i understood from this question is :

We take any path from source to dest( s to d ) at the end all intermediate vertices will get cancel out subsequently .

Hence the weight of vertices doesn't matter for computing shortest path .

But now let's consider that we are also intrested in Final Cost also :

Suppose before applying new function criteria , we have 3 path p1,p2 and p3 from source to dest with each carry cost of c1,c2and c3 (& assume p2 is best path  it mean c2 < c1 & c2 < c3)

Now when we assign some weight to the vertices new path remain same but cost will get change as follow :

c1'  =  c1 + cost(s)-cost(d)

c2' = c2 + cost(s) - cost(d)

c3' = c3 + cost(s) - cost(d)

 

So conclusion : Shortest path in terms of direction or edges will not get changed but the overall cost get changed.

 

Correct me if I missed anything  !

Thanks !!

---

Thanks a lot bro .

---

Refer to these answers for better understanding  

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

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

Extending @Deepak Poonia sir's comment

If we add some constant $k$ with every $w(u,v)$ then in the resulting graph the sortest path from $s$ to any vertex $d$ may change. But if we add some constant $k$ with every path length from $s$ to $d$ then the sortest path does not change.

Length of path $P:s-v_1-v_2-d=6$

Length of path $Q:s-v_3-v_4-v_5-v_6-d=5$

In this question we are effectively adding weight of $f(s)-f(d)$ in path $P$ and $Q$.

---

@Gopal6854 Thanks man..

---

A picture is worth 1000 words

Answer 2

Some important concepts - 

(Note that the question is asking for shortest paths and not single source shortest path)
Consider this directed weighted graph - 

What is the shortest Path from A to C and its cost?

A->B->C , cost = 2.

But, as there is a negative edge weight(B to C), running Dijkshtra Algorithm may give wrong result. Thus, we have to use Bellman Ford algorithm with is asymptotically costlier than Dijkshtra.

So, now can we think of a solution so that we can apply Dijskhtra on this graph and get the correct Shortest path?

One solution is to add 3 to all edges, so negative edge weight becomes non negative.

The edge weights would become- 

Notice here that the shortest path has been changed. The new shortest path is A->C with cost of 6.

So this solution changes the shortest path itself.

Another solution - Reweighting.

Assign weights to the vertices (assigned in green)

Now, after reweighting the edges as  -> w(u,v) + f(u) - f(v)  we get -

Notice that shortest path from A to C remains unchanged but COST of the shortest path has changed from 2 to 8 . 

More Analysis- 
If we observe carefully, the shortest path from A to C consists of 2 edges, A to B(e1) and B to C(e2)

Thus, cost of total path is e1 + e2 . 
Now, before reweighting, e1 + e2 = 2.

After reweigthing, 

e1  = 5 + f(A)  - f(B)

e2 = (-3) + (B) - f(C)

Thus, e1+ e2 = 5 + f(A) - f(B) + (-3) + f(B) - f(C).

Therefore, e1 + e2 = 5-3+f(A) -f(C)

e1 + e2 = 2 + 10 - 4

e1 + e2 = 8.

Here, the intermediate vertex B's weight got cancelled out. Thus, what matters is only the weights of source and destination vertices  in the  shortest path.
Thus, whatever weights we assign to the vertices(positive/negative), the shortest PATHS wont change, but shortest path COST will change.

Hence option A is correct.

---

This Question is based on the concepts used in  JOHNSON'S ALGORITHM which is  used to find the shortest paths between all pairs of vertices in a weighted, directed graph. It is particularly useful for sparse graphs that contain negative-weight edges but do not have negative-weight cycles.

ref - https://www.geeksforgeeks.org/johnsons-algorithm/

 

Comments

WOW Explanation !!!!

---

Great Explanation

---

Great Explanation Sir!

Answer 3

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. 

---

The shortest path does not change but the value of the shortest path will change right in case of w' and that will be f(s) - f(d) more then old path right ?

---

@Deepak Poonia Sir

's' is the new vertex added and edge: s-u with edge weight = 0
How can this be negative even though graph edges in the original graph (G) can be any real number?

 

Answer 4

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 5

Here is an example to claim the point : 

Answer 6

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.

Comments

w'(u,v) = w(u,v) + f(v) it doesn't depend on the source node