Perform Dijkstra on graph with negative edges by adding a big enough constant to every edges

Question

I know that this doesn't work because shortest path with a lot of edges may have bigger weight than a longer path with less edges. But what if, you keep track of the edges that our current weight path on each node and when we compare we subtract the number of edges on this path * the constant so that we get the original weight. I understand there is also the negative cycles problem, but is there an efficient algorithm that tell if a graph contains a negative cycle ?

Answer 1

It's called Johnson's algorithm.

Instead of trying to keep track of the number of edges, it searches for a function $\delta:V\to \mathbb R$ so that for all edge $(v,v')$, $w(v,v')+\delta(v)-\delta(v')\ge 0$ and set that as the new weight $w'(e,e')$ of the edge $(e,e')$.

Then, for any path $p=v_1\cdot \dots\cdot v_n$ the $\delta$ values of all intermediate vertices cancel so that $w'(p)=w(p)+\delta(v_1)-\delta(v_n)$. And the shortest paths for $w$ and $w'$ therefore coincide.

Then remains the problem of finding such a $\delta$. The magic is that you can just add a new vertex $v_*$ and edges $(v_*,v)$ of weight $0$ for every vertex $v$, and then set $\delta (v)$ to be the weight of a shortest path $p_v$ from $v_*$ to $v$. Then the positiveness condition simply becomes $w(v,v')+w(p_v)-w(p_{v'})\ge 0$ which can be rewritten as $w(p_v)+w(v,v')\ge w(p_{v'})$ which is true because $p_v\cdot v'$ is a path from $v_*$ to $v'$ and $p_{v'}$ is a path from $v_*$ to $v'$ of minimal weight.