[Solved]: Normalizing edge weights and the effect on Dijkstra's algorithm

Problem Detail: 

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.

Asked By : ILoveCliques

Answered By : A.Schulz

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41869