retagged by
17,830 views
39 votes
39 votes

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,_____________”.

  1. for every $f: V \rightarrow \mathbb{R}$
  2. if and only if $\forall u \in V, \: f(u)$ is positive
  3. if and only if $\forall u \in V, \: f(u)$ is negative
  4. 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$
retagged by

6 Answers

Best answer
32 votes
32 votes
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.
selected by
15 votes
15 votes

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.

edited by
8 votes
8 votes

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.

edited by
4 votes
4 votes
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.
Answer:

Related questions

8 votes
8 votes
4 answers
2
Arjun asked Feb 12, 2020
9,633 views
Consider a graph $G = (V,E)$, where $V = \{v_1,v_2, \dots ,v_{100}\}$, $E = \{(v_i,v_j) \mid 1\leq i < j \leq 100\}$, and weight of the edge $(v_i,v_j)$ is $\mid i – j ...