APSP - Johnsons Algorithm

Reweighting

Intuition: if we convert the edge weight to be positive, then we can use Dijkstra’s Algorithm on all vertexes to compute all pair shortest path.

Reweighting cannot change the shortest path $p$ for any vertex $i,j$. That is, the shortest path between any $i,j$ must remain unchange after reweighting. Second, reweighting must preserve negative cycle.

$G=(V,E)$, for all edge $(u,v)\in E$, define $\bar{w}(u,v)=w(u,v)+h(u)-h(v)$, where $h(u)$ is the shortest path from a super external source $s$ which connects to evert vertexes $v\in V$ (or any vertex that reaches every other vertexes), as the graph shows.

source : wiki

Correctness

Consider vertex $v$, $h(v)$ is the shortest path length from $s$, then by the definition of shortest path, we know $h(u)+w(u,v)\le h(v)\Rightarrow w(u,v)+h(u)-h(v)\ge 0$

For a shortest path $p=(v_0,v_1,\cdots ,v_k)$, $\begin{array}{rl}\bar{w}(p)& =\bar{w}(v_0,v_1)+\bar{w}(v_1,v_2)+\cdots +\bar{w}(v_{k-1},v_k)\\ & =(w(v_0,v_1)+h(v_0)-h(v_1))+(w(v_1,v_2)+h(v_1)-h(v_2))+\cdots +(w(v_{k-1},v_k)+h(v_{k-1})-h(v_k))\\ & =w(v_0,v_1)+w(v_1,v_2)+\cdots +w(v_{k-1},v_k)+h(0)+h(k)\\ & =w(p)+h(0)+h(k)\end{array}$

proof the shortest path property unchanged by contradiction

Assume that there is another shortest path $p^{\prime }$, with $\bar{w}(p^{\prime })<\bar{w}(p)$. Then $\bar{w}(p^{\prime })=w(p^{\prime })+h(0)+h(k)<\bar{w}(p)=w(p)+h(0)+h(k)\Rightarrow w(p^{\prime })<w(p)$, which is a contradiction, because $w(p)$ is the original shortest path, there is no way other path length would be shorter than that.

Proof of negative cycle preservation after reweighting

For this cycle $c=(v_0,v_1,\cdots ,v_k,v_0)$, $\bar{w}(c)=w(c)+h(0)-h(0)=w(c)<0$