Johnson 全源最短路算法

​ Johnson 全源最短路是一种允许带负权边的全源最短路算法。它的主要实现思路即为将原先带负权边的图转化成求一个无负权边的图的全源最短路。

​ 我们定义一个新节点 \(0\)，其中 \(0\) 节点与其它各节点连接一条边权为 \(0\) 的边。令 \(h_i\) 为 \(0\) 节点到 \(i\) 节点的最短路。

​ 约定记号 \(E\) 为原图边集，\(E'\) 为新图边集。对于任意 \((u,v,w)\in E\)，我们将 \((u, v, w + h[u] - h[v])\) 加入 \(E'\) 中。对 \(E'\) 求解，其中 \(\mathrm{dis}(u,v)=\mathrm{dis'}(u,v)-(h[u]-h[v])\)。

​ 算法正确性是不难而知的。首先，\(h\) 函数满足三角形不等式，即 \(h[u]+w(u,v)\geq h[v]\)，推出 \(w + h[u]-h[v] \geq 0\)，说明无负权边。其次，对于任意一条从 \(s\) 到 \(t\) 的路径，它的最短路长度为原图最短路长度加上 \(h[s]-h[t]\)。或者，换一种理解方式，\(h\) 函数为节点的势能函数，即可的。

​ 算法瓶颈在无负权图求全源最短路，可以用 Dijkstra 来实现到 \(\mathcal{O}(nm\log n)\)。