Let \(G = (V,E)\) be a directed, weighted graph with weight function \(w: E…
2020
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)∈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\)
Attempted by 80 students.
Show answer & explanation
Correct answer: A
Key identity: for any path P from vertex x to vertex y we have w'(P) = w(P) + f(x) - f(y).
Why this implies preservation of shortest paths:
For fixed endpoints x and y, the term f(x)−f(y) is the same for every path from x to y.
Therefore, comparing two paths between x and y, their reweighted costs differ by the same amount as their original costs, so the ordering of path costs is unchanged.
Consequently, any shortest path between a given pair of vertices under the original weights remains a shortest path between the same pair under the reweighted weights. This holds for every choice of f.
Note: The construction described using distances from a new source is the standard choice of potentials in Johnson's algorithm because it makes all reweighted edge weights nonnegative, which allows running Dijkstra. That nonnegativity is useful algorithmically but is not required for preservation of shortest paths.