-1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Couldn't this create a negative cycle? $\endgroup$
    – usul
    Oct 3, 2015 at 15:39
  • $\begingroup$ Can we just assume that w(u, v) is always positive? $\endgroup$
    – xxx222
    Oct 3, 2015 at 16:05

1 Answer 1

5
$\begingroup$

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.)

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.