Johnson 全源最短路算法学习笔记

由 hycqwq 发布

Floyd 算法可以以 $O(n^3)$ 的时间求得图上全源最短路。然而这个复杂度在许多题目中是不可接受的。这时我们可以使用另外一种全源最短路算法 Johnson。

Johnson 全源最短路径算法 - OI Wiki

引入

考虑到全源最短路就相当于对每个节点跑一边单源最短路,我们尝试在 $n$ 次单源最短路的基础上做一些优化。

跑 $n$ 次 Dijkstra,总复杂度为 $O(nm \log m)$,这在部分稀疏图上的效率比 Floyd 更好,但是无法处理负边权的情况。

于是我们希望通过一些手段来改造图,使得在不影响最短路的情况下把所有边权改造成非负数。

算法流程

建立一个点 $X$,从 $X$ 向其它所有点连接一条边权为 $0$ 的边。使用 SPFA 计算从 $X$ 出发的单源最短路,记为 $d_i$。

对于一条边 $(u, v, w)$,将其边权 $w$ 重设为 $w + d_u - d_v$,这样可以保证 $w$ 为非负数。

接下来跑 $n$ 次 Dijkstra 即可求出全源最短路。

对处理后所有边权均为非负数的证明

对于一条边 $(u, v, w)$,有 $d_v \le d_u + w$(参考 SPFA/Dij 的最短路更新思路),于是 $w + d_u - d_v \ge 0$。

对算法正确性的证明

假设 $w_e, p_e$ 分别为边 $e$ 修改后和修改前的边权。

算法处理过后的图上的一条路径 $(E_1, E_2, \dots, E_x)$ 的长度为:

$$ \begin{aligned} & \sum_{i=1}^x w_i \\ =& (p_1 + d_{u_1} - d_{v_1}) + (p_2 + d_{v_1} - d_{v_2}) + \dots + (p_x + d_{v_{x - 1}} - d_{v_x}) \\ =& (\sum_{i=1}^x p_i) + d_{u_1} - d_{v_x} \end{aligned} $$

而对于和这条路径同起终点的路径,$d_{u_1} - d_{v_x}$ 为定值,不会影响最短路径的计算。

将这个结论推广到图中所有边上即可证明算法正确性。


暂无评论

发表评论