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

Thanks a lot bro .

---

Refer to these answers for better understanding  

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

---

Add everything and you'll realise that the final cost depends on starting and final vertices only and nothing depends on intermediary nodes. So shortest path won't really change. 

Answer 1

 

Option A is correct.

 

There is a graph G, let us consider G is this.

Notice in the question there are two functions w, w’ which are assigning weights to the graph.The question already assumes that their shortest paths are same in both w, w’ now they want to find what can be possible.

 

Now if we add some positive number to all the edges to every edge of graph G given here then we may change the shortest path E.g. add 2 to all the edges in G

This is why option B can not be the answer.

 

The same thing will happen if we add some negative number to all the edges then also we will find that shortest paths is changing.

This is why option C can not be the answer.

So we get that we can not add some +ve number also we can not add some -ve number to the previous weights(assigned by w). [Basically , w(u,v) = w’(u,v)]

We have left with one thing only that f(u) - f(v) = 0;

So, f(v) = f(u), for all (u, v) $\epsilon$ E.

This can be satisfied in many ways, E.g. lets take f: V→ R and f(u) = some constant , $\forall$ u $\epsilon$ V. 

So option A is correct

 

 

Now we will talk about option D, here we are adding a new vertex S to G, 

Also f(u) = 0,  u $\epsilon$ V  because  distance(S, u) = 0

Here also  f(v) = f(u), for all (u, v) $\epsilon$ E, is satisfying but this is not the only way.

The condition given is sufficient but not necessary. So “if and only if“ is wrong.

 

Answer 2

I am writing what I understood from Algorithms by CLRS,

w'(u,v) is a simple transformation of w(u,v)

1) Let G' be the graph with weight function w' on its edges and G be the graph with weight function w on its edges.

2) This transformation is such that the following lemma holds:

(see simple proofs given in book)

lemma 1: The shortest path between any pair of vertices in G will be the same in G'

lemma 2: If G has negative weight cycles then G' also has negative weight cycles and vice versa. (in short "if and only if")

corollary from lemma 2: If G has no negative weight cycles then G' also has no negative weight cycles and vice versa. (in short "if and only if")

So the answer is A) for every f:V -> R

Comments

What is CLRS ? ? ?

---

Cormen book

Some preview  here

Answer 3

How good of a question this is. Here because we are adding Fu - Fv this means that when we do it for any shortest path there -Fv will be cancelled by the Fv because this will be the new Fu for the next edge. Like this way we can will eventually cancel out all the terms and only Fu - Fx would remain where x is the the destination vertex itself. Now you can clearly see we are just adding the same quantity that is Fsource - Fdestination to all the edges which wont affect the shortest paths at all. Hence the paths shortest paths would be retained.

Comments

The key point here is :

We don't increment every path from u to v by f(u)-f(v)   [ ∵Those terms will get cancelled out while calculating w'(u,v) ]