Say that $G'$ is a graph re-weighted from $G$ using the rule: $w' (u, v) = w(u, v) − f(u) + f(v)$, where $f$ always produce the positive results for any nodes. Can we prove that the shortest path $P_G$ from $s$ to $t$ remains the shortest path from $s$ to $t$ in $G'$?
1 Answer
$\begingroup$
$\endgroup$
0
Yes, because any path from $s$ to $t$ of weight $w$ in $G$ will have weight $w - f(s) + f(t)$ in $G'$. This is the Edmonds-Karp trick for solving minimum-cost flow problems, see Section 2 of the paper "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems".
(I would post this as a comment, but I don't have enough reputation for it.)