Floyd–Warshall 最短路算法

Floyd–Warshall 求所有顶点对之间的最短距离，允许负边权。若某条路线可以经过负环，其长度就没有有限下界；以下递推的有限最短路解释以不存在负环为前提。

动态规划状态

将顶点编号为 $0,\ldots,n-1$。设 $D_k[i,j]$ 为只允许编号小于 $k$ 的顶点作为内部顶点时，从 $i$ 到 $j$ 的最短距离。

加入顶点 $k$ 后，最优路径或者不经过它，或者分为 $i\to k$ 与 $k\to j$ 两段：

$$D_{k+1}[i,j]=\min(D_k[i,j],D_k[i,k]+D_k[k,j]).$$

初始矩阵包含直接边和对角线上的零；重边取最小权值。负自环不能被对角线初始化覆盖。枚举中间顶点的循环必须放在最外层。

实现

from math import inf

def floyd_warshall(n, edges):
    dist = [[inf] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, weight in edges:
        dist[u][v] = min(dist[u][v], weight)
    for k in range(n):
        for i in range(n):
            if dist[i][k] == inf:
                continue
            for j in range(n):
                if dist[k][j] != inf:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

无负环时，原地更新不会改变本轮所需的第 $k$ 行和第 $k$ 列的距离，因为 $d[k][k]=0$，因此可以省去动态规划的阶段维度。

时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。适用规模取决于语言与时限，不能只凭固定的顶点数阈值判断。

负环的影响

计算后若某个 $d[k][k]<0$，则存在负环。对所有能到达该 $k$、且从该 $k$ 能到达的点对 $(i,j)$，最短距离应解释为负无穷，而不是数组中的有限数值。上面的代码保留原始矩阵，调用者须检查对角线后再使用结果。