最短路

Johnson 最短路

新建一个虚拟节点 0，然后从该点向其他点连权值为 0 的有向边。
接下来使用 Bellman-Ford（SPFA）算法求出 0 号点到其他所有点的最短路，记为 。
假设存在一条 到 ，边权为 的边，那么将该边重新定义为 。
然后从起点开始跑最短路即可。该算法可以求解带有负权边（但没有负环的）的最短路问题。
证明：

另外，根据三角不等式，任意一边都满足：，重新标记后有 ，所以就证明了新图上的边权非负。