GATE CS 2020 Q40 — Shortest Paths (Dijkstra, Bellman-Ford)

Let $P = (v_0, v_1, \dots, v_k)$ be any path from a start vertex $u = v_0$ to an end vertex $v = v_k$. The weight of the path $P$ under the new weight function $w'$ is given by:

Expanding this sum, the terms involving $f$ form a telescoping series:

For any two vertices $u$ and $v$, the term $f(u) - f(v)$ is a constant that depends only on the endpoints $u$ and $v$, and not on the specific path chosen between them.

Therefore, for any two paths $P_1$ and $P_2$ from $u$ to $v$:

This preservation of relative path weights ensures that a path is a shortest path under $w$ if and only if it is a shortest path under $w'$. Since this property holds regardless of the values assigned by $f$, it is true for every $f: V \rightarrow \mathbb{R}$.