Johnson 全源最短路算法

形式陈述 ​

输入是有限有向图 $G=(V,E)$ 与实边权 $w$，允许负边但不允许负权环；输出每对可达顶点 $u,v$ 的最短距离公理库最短路问题Shortest-path problem在带边代价图中寻找两点之间总代价最小路径的问题。。添加超级源 $q$，向每个 $v\in V$ 连零权边，运行 Bellman–Ford公理库Bellman–Ford 算法Bellman–Ford algorithm通过反复松弛边求含负权边图的单源最短路并检测可达负环。。若检测到负环则报告距离问题无定义；否则令

$$h(v)=\delta (q,v),w^{\prime }(u,v)=w(u,v)+h(u)-h(v).$$

最短路三角不等式 $h(v)\le h(u)+w(u,v)$ 保证每条 $w^{\prime }(u,v)\ge 0$。随后以每个 $u$ 为源在 $w^{\prime }$ 上运行 Dijkstra公理库Dijkstra 算法Dijkstra's algorithm在非负边权图中逐次确定最短距离的单源最短路算法。，得到 $d_u^{\prime }(v)$，再恢复

$$d_u(v)=d_u^{\prime }(v)-h(u)+h(v).$$

任意 $u$ 到 $v$ 路径 $P$ 的中间势函数逐项抵消，满足 $w^{\prime }(P)=w(P)+h(u)-h(v)$；同端点路径都加同一常数，因此最短者不变。二叉堆和邻接表下总时间为 $O(VE+V(E+V)\log V)$，空间除输出矩阵外为 $O(V+E)$。

直觉 ​

势函数给每个顶点换一个高度零点。单条边的坡度随两端高度改变，但一条完整路径的变化只由起终点决定；所以可以消除局部负边，而不改变同一对端点之间的路径排名。非负新权让 Dijkstra 可用，最后再撤销端点偏移。

Bellman–Ford 不只是预处理负边，它同时生成保证非负性的可行势，并充当负环证书。随意选择 $h$ 可能仍留下负边，使后续贪心定型失效。

例子与边界 ​

设边 $a\to b$ 权 $-2$、$b\to c$ 权 $3$、$a\to c$ 权 $4$。加超级源后可得 $h(a)=0,h(b)=-2,h(c)=0$，于是三条新权分别为 $0,1,4$。Dijkstra 在新图求得 $d_a^{\prime }(c)=1$，恢复后仍为 $1-h(a)+h(c)=1$，对应原图路径 $a\to b\to c$。

若图含可达负环，某些端点间可以绕环任意降低路径权，距离不是有限值；算法必须停止，不能继续重赋权。不可达点在各次 Dijkstra 中保持无穷，恢复公式也不能对无穷做普通实数运算。

重赋权只保留路径总权的相对次序，不保留每条边原值。输出若需要路径长度必须恢复，若需要具体路径则保存每次 Dijkstra 的前驱即可，因为最短路径的边序列没有改变。

推论与应用 ​

Johnson 适合边数远小于 $V^2$、存在负边但无负环的全源最短路。稠密图上 Floyd–Warshall 的 $O(V^3)$ 简洁界可能更合适；算法选择应同时考虑图密度和堆实现。

势函数重赋权也出现在最小费用流等算法中。可复用的核心不是“先跑一次 Bellman–Ford”的步骤表，而是端点伸缩不变量与所有残余边非负的证明。

参考资料

• Donald B. Johnson, “Efficient Algorithms for Shortest Paths in Sparse Networks,” Journal of the ACM 24(1), 1977, pp. 1–13.
• Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, §23.3.