If I had a graph $G$ with some negative edge weights, clearly Dijkstra's algorithm does not definitely halt, since it might get caught in a negative cycle (shedding infinite weight). However, would finding the minimum weight (most negative weight) $w$ and adding the absolute value to every edge's weight preserve the shortest path, and get rid of the possibility of a negative cycle in one fell swoop? I can't seem to find any good literature on this, which makes me think that it can't be true.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I believe you can find your answer here: cs.stackexchange.com/questions/19771/… $\endgroup$– Francesco GramanoCommented Apr 26, 2015 at 22:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Your idea does not work. Adding an absolute value to every edge wont preserve shortest paths. To see this take this graph:
u------v
| |
| |
a------b
with all edge weights 1 except for $uv$ where the weight is 4. The shortest $uv$ path goes via $u \to a \to \to b \to v$. But if you add a +2 to every edge, the sortest $uv$ path is $u\to v$.
There is however a reweighting scheme that works. Check out Johnson's algorithm, which is built around this. Simply speaking: add a dummy vertex $x$ connected to all other vertices with a zero weight edge and add to every weight of an edge $(i,j)$ the value $d(x,i) - d(x,j)$.
