Let G = (V, E) be a directed, weighted graph with weight function w: E→R.
For some function f: V→R, for each edge (u, v) ∈ 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,_____".
for every f: V→R
if and only if ∀ u ∈ V, f(u) is positive
if and only if ∀ u ∈ V, f(u) is negative
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
For any mapping of vertices to real values, the shortest paths won't change. All intermediate node 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.
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. 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.
Solution Reference: Gateoverflow