Floyd-Warshall 算法详解：原理、代码与复杂度

Floyd-Warshall 解决什么问题

有时你需要的是所有地点两两之间的距离，而不只是从某一个起点出发：所有城市之间的行程时间表、每对服务器之间的延迟，或依赖图的完整可达关系。Floyd-Warshall 用一个非常简短的动态规划算法解决了这个全源最短路径问题。

它由 Robert Floyd 于 1962 年发表（《Algorithm 97: Shortest path》），建立在 Stephen Warshall 同年提出的传递闭包算法之上。

用大白话讲思路

把节点编号为 0 到 V − 1。处理完节点 k 之后，dist[i][j] 就是只允许使用节点 0 到 k 作为中转点时，i 到 j 的最短路径。再允许多一个中转点 k，有两种选择：不经过 k 的原最优路径，或者由两段最优路径拼成的 i → k → j（这两段只使用 k 之前的节点）。

1. 填充矩阵：对角线为 0，有边的位置填边权，其余位置填无穷大。
2. 对 k = 0 到 V − 1，遍历每一对 (i, j)：如果 dist[i][k] + dist[k][j] < dist[i][j]，就更新它。
3. 最后一个 k 处理完后，矩阵中就是所有最短距离。对角线上出现负数表示存在负环。

循环的顺序至关重要：k 必须是最外层循环。

逐步演示一个例子

有向图含 4 个节点，边为 0→1（3）、0→3（7）、1→0（8）、1→2（2）、2→0（5）、2→3（1）、3→0（2）。初始矩阵（行为起点，列为终点）：

1. k = 0：路径可以经过节点 0。1→3 变为 8 + 7 = 15，2→1 变为 5 + 3 = 8，3→1 变为 2 + 3 = 5。
2. k = 1：经过节点 1。0→2 变为 3 + 2 = 5，3→2 变为 5 + 2 = 7。
3. k = 2：经过节点 2。0→3 从 7 改进为 5 + 1 = 6，1→3 从 15 改进为 2 + 1 = 3，1→0 从 8 改进为 2 + 5 = 7。
4. k = 3：经过节点 3。1→0 从 7 改进为 3 + 2 = 5，2→0 从 5 改进为 1 + 2 = 3，2→1 从 8 改进为 1 + 5 = 6。

最终矩阵各行：0 → [0, 3, 5, 6]，1 → [5, 0, 2, 3]，2 → [3, 6, 0, 1]，3 → [2, 5, 7, 0]。

Python 实现

INF = float("inf")
def floyd_warshall(n, edges):
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[j if i == j else None for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt
edges = [(0, 1, 3), (0, 3, 7), (1, 0, 8), (1, 2, 2),
         (2, 0, 5), (2, 3, 1), (3, 0, 2)]
dist, nxt = floyd_warshall(4, edges)
for row in dist:
    print(row)
# [0, 3, 5, 6]
# [5, 0, 2, 3]
# [3, 6, 0, 1]
# [2, 5, 7, 0]

nxt 矩阵保存 i 到 j 最优路径上的第一步，足以还原任意一条路径：

def path(nxt, i, j):
    if nxt[i][j] is None:
        return []                         # no path
    route = [i]
    while i != j:
        i = nxt[i][j]
        route.append(i)
    return route
print(path(nxt, 1, 0))  # [1, 2, 3, 0]

如果节点很多又想在 Python 中提速，可以用 NumPy 把同样的三重循环写成每个 k 一次向量化更新：d = np.minimum(d, d[:, k, None] + d[None, k, :])。

时间与空间复杂度

对于边权非负的稀疏图，从每个节点各运行一次 Dijkstra 的开销是 O(V × (V + E) log V)；当 E 远小于 V² 时，比 O(V³) 更快。

变体与常见错误

• 负环：循环结束后，如果某个 i 满足 dist[i][i] < 0，说明节点 i 位于负环上，经过它的最短路径没有定义。
• 传递闭包（Warshall）：改用布尔值，把 min/加法换成 或/与：reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])。
• 极小化最大值与极大化最小值路径：把 + 换成 max（或 min），例如求最大边权尽可能小的路径。
• 只有在确定两个“无穷大”相加不会溢出时，才用一个很大的有限数代替无穷大；在 Python 中，float("inf") 是安全的选择。
• 把对角线初始化为 0；遇到平行边时，保留权最小的那条。

何时使用及实际应用

• 预先计算所有车站、仓库或城市之间的距离表，供以后查询。
• 图分析，例如小型网络的接近中心性或直径。
• 面试题：找出在距离阈值内邻居数最少的城市、除法求值（比值即路径乘积）、把课程先修关系视为传递闭包。