Let be a directed, weighted graph with weight function .
For some function , for each edge , define as
Which one of the options completes the following sentence so that it is TRUE?
"The shortest paths in under are shortest paths under too, ___."
for every
if and only if , is positive
if and only if , is negative
if and only if is the distance from to in the graph obtained by adding a new vertex to and edges of zero weight from to every vertex of
ANSWER
The shortest paths in G under w are shortest paths under w' too, for every f : V -> R -- option (A).
Official answer: ASource: Official answer key, GATE 2020 CS (IIT Delhi)
Take any directed path P from a fixed vertex u to a fixed vertex v, passing through u = x_0, x_1, ..., x_k = v.
By definition of w', its total weight along P is w'(P) = sum_{i=0}^{k-1} (w(x_i,x_{i+1}) + f(x_i) - f(x_{i+1})).
The f-terms telescope: sum_{i=0}^{k-1} (f(x_i) - f(x_{i+1})) = f(x_0) - f(x_k) = f(u) - f(v), since every intermediate f(x_i) cancels once with + and once with -.
So w'(P) = w(P) + (f(u) - f(v)) for EVERY path P from u to v -- the extra term depends only on the endpoints u, v, never on which path or intermediate vertices are chosen.
Adding the same constant f(u)-f(v) to the weight of every candidate u-to-v path is an order-preserving shift: it can never change which path(s) among them have minimum total weight, regardless of the sign of f(u)-f(v).
Hence the shortest path between any fixed pair of vertices is identical under w and under w'.
Nothing in this argument restricted f to being positive, negative, or a specific distance function -- it holds for every f : V -> R, matching option (A) and ruling out the unnecessary conditions in (B), (C) and (D).
KEY IDEA
Reweighting every edge (u,v) by w'(u,v) = w(u,v) + f(u) - f(v) changes the total weight of ANY path P from a fixed u to a fixed v by exactly the same constant f(u) - f(v) (the intermediate f-terms telescope away), regardless of which internal vertices P visits. Since a constant additive shift applied identically to every competing u-to-v path can never change which of them has the smallest total weight, the set of shortest paths between any pair of vertices is identical under w and under w' -- for every choice of f, with no sign restriction and no special construction required.
WATCH OUT FOR
Students assume Johnson's algorithm's specific choice of f (the shortest-distance-from-an-added-source construction, option D) is necessary for shortest paths to be preserved, because that is the f used in practice. In fact that construction is only needed to make w' nonnegative so Dijkstra becomes usable -- a separate, additional goal. Preservation of shortest paths itself holds for every f with no restriction, since the endpoint-only additive shift is order-preserving regardless of its sign.
From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes
