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'$?



Shortest path problem
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.)


