Floyd 算法可以以 $O(n^3)$ 的时间求得图上全源最短路。然而这个复杂度在许多题目中是不可接受的。这时我们可以使用另外一种全源最短路算法 Johnson。
引入
考虑到全源最短路就相当于对每个节点跑一边单源最短路，我们尝试在 $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}$ 为定值，不会影响最短路径的计算。
将这个结论推广到图中所有边上即可证明算法正确性。