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) 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 -> R B. if and only if f is a positive function, i.e., f(v) > 0 for every v in V C. if and only if f(u) <= f(v) for every edge (u, v) in E D. if and only if f is a negative function, i.e., f(v) < 0 for every v in V
GATE 2020 · Algorithms · Shortest Path · medium
Answer: A. for every f : V -> R — the reweighting is a telescoping transformation that preserves shortest path structure unconditionally.
- Compute reweighted path length (telescoping sum): For path p = v_0 -> v_1 -> ... -> v_k: w'(p) = [w(v0,v1)+f(v0)-f(v1)] + [w(v1,v2)+f(v1)-f(v2)] + ... + [w(v_{k-1},v_k)+f(v_{k-1})-f(v_k)] = w(p) + f(v_0) - f(v_k) All intermediate f terms cancel (telescoping). So w'(p) = w(p) + f(s) - f(t).
- Show shortest paths are preserved for any f: For any two paths p1, p2 from s to t: w'(p1) = w(p1) + f(s) - f(t) w'(p2) = w(p2) + f(s) - f(t) So w'(p1) - w'(p2) = w(p1) - w(p2). A path is shorter under w if and only if it is shorter under w'. This holds for EVERY f: V -> R, with no restriction on f being positive, negative, or satisfying any inequality.