Q) 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}'(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$
For the given question, answer is given as (A) but according to me, (A) is not correct. I have taken one example as :
Here, shortest path from (1) to (3) is (1) $\rightarrow$ (2) $\rightarrow$ (3) :
under weight function $w$ is : $1 -3 = -2$
under weight function $w'$ is : $1 + f(1) - f(2) -3 + f(2) - f(3) = 1 + f(1) - f(3)$
Now if I consider option (A), then it should be correct for all $f(1)$ and $f(3)$ but if $f(1) \neq f(3)$ then it should not be correct. For examle $f(1) = 3$ and $f(3) = 5$
Please help.
Suppose that $P=(v_i)_{i=0}^n$ is a path in $G$. The length of $P$ under $w$ is given by $$w(P) = \sum_{i=1}^n w(v_{i-1}, v_i)$$ The length of $P$ under $w'$ is given by
$$\begin{align}w'(P) &= \sum_{i=1}^n w'(v_{i-1}, v_i)\\ &= \sum_{i=1}^n [w(v_{i-1}, v_i) + f(v_{i-1}) - f(v_i)]\\ &= \sum_{i=1}^n w(v_{i-1}, v_i) + \sum_{i=1}^nf(v_{i-1}) - \sum_{i=1}^n f(v_i)\\ &= w(P) + f(v_0) - f(v_n)\end{align}$$
Ergo, for any two paths $P$ and $Q$ from vertex $u$ to $v$, $$w'(P) = w(P) + f(u) - f(v)\\w'(Q) = w(Q) + f(u) - f(v)$$ Since $w'$ adds the same constant value to the $w$-lengths of all paths from $u$ to $v$, the shortest path under $w$ will also be the shortest path under $w'$.