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^{\prime}(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^{\prime}$ too, ___________”.

Let $P = (v_0, v_1, v_2, \dots, v_k)$ be any directed path from vertex $u = v_0$ to vertex $v = v_k$.

The total weight of path $P$ under the modified weight function $w^{\prime}$ is given by the telescoping sum:

Notice that the extra term $f(u) - f(v)$ depends solely on the source $u$ and target $v$, and is identical for all paths between $u$ and $v$. Adding a constant value to every path between $u$ and $v$ does not change their relative ordering in weight.

Therefore, a path between $u$ and $v$ minimizes $w(P)$ if and only if it minimizes $w^{\prime}(P)$. This property holds for every function $f: V \rightarrow \mathbb{R}$, making A the correct choice (this is the reweighting technique used in Johnson's algorithm).