Floyd-Warshall算法中循环顺序的关键：理解状态依赖性

Floyd-Warshall算法是解决所有节点对最短路径问题的经典动态规划算法，其时间复杂度为O(n³)，适用于带权有向图（也支持无向图，因为无向边可视为两条方向相反的有向边），并且能够正确处理边权为负数的情况，但不能存在负权回路。很多初学者在编写该算法时，容易忽略循环的嵌套顺序，导致结果错误，核心原因就是对算法的状态依赖关系理解不到位。

算法核心思想

Floyd-Warshall算法基于动态规划思路，定义状态dp[k][i][j]表示：只允许经过编号不超过k的中间节点时，从节点i到节点j的最短路径长度。我们最终需要的结果是dp[n-1][i][j]（假设节点编号从0到n-1），也就是允许经过所有节点时的最短路径。

状态转移方程为：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])，含义是：要么不经过第k个节点，最短路径就是上一轮（只允许经过前k-1个节点）的结果；要么经过第k个节点，拆分成从i到k和从k到j两段路径，取两者中的最小值。

为了优化空间复杂度，我们可以压缩掉第一维的k，直接用dist[i][j]表示当前轮次的最短路径，每一轮更新后，dist[i][j]就等价于dp[k][i][j]。但此时循环顺序就变得至关重要。

正确的循环顺序

Floyd-Warshall算法的正确循环顺序是：最外层循环遍历中间节点k，中间层循环遍历起点i，最内层循环遍历终点j。代码示例如下：

def floyd_warshall(n, edges):
    # 初始化距离矩阵，n为节点数，edges为边列表，格式为(u, v, w)表示u到v的边权为w
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    # 对角线初始化为0，自己到自己的距离为0
    for i in range(n):
        dist[i][i] = 0
    # 初始化已知边
    for u, v, w in edges:
        dist[u][v] = w
    # 核心循环：最外层遍历中间节点k
    for k in range(n):
        # 中间层遍历起点i
        for i in range(n):
            # 最内层遍历终点j
            for j in range(n):
                # 如果经过k的路径更短，则更新
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# 测试示例：3个节点，边为0->1权2，1->2权3，0->2权10
n = 3
edges = [(0, 1, 2), (1, 2, 3), (0, 2, 10)]
result = floyd_warshall(n, edges)
# 输出结果，result[0][2]应该是5（0->1->2）
print(result[0][2])

上述代码中，最外层循环变量k代表当前允许使用的中间节点上限，每一轮k的循环中，我们都在用前一轮（k-1）的距离数据来更新当前轮（k）的距离数据。因为更新dist[i][j]时，依赖的是dist[i][k]和dist[k][j]，而这两个值如果在当前k轮已经被更新过，就意味着它们已经允许经过k作为中间节点，此时再用它们去更新其他路径，就会错误地允许路径经过两个k节点，违背状态定义。

把k放在最外层，就能保证每一轮更新dist[i][j]时，用到的dist[i][k]和dist[k][j]都是只允许经过前k-1个中间节点的结果，不会出现重复经过k的情况，符合状态转移的逻辑。

错误循环顺序的问题

如果把循环顺序改成最外层i、中间层j、最内层k，或者最外层i、中间层k、最内层j，都会得到错误结果。我们可以用最外层i、中间层j、最内层k的顺序来举例说明：

def wrong_floyd(n, edges):
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
    # 错误的循环顺序：最外层i，中间层j，最内层k
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# 同样的测试示例
n = 3
edges = [(0, 1, 2), (1, 2, 3), (0, 2, 10)]
wrong_result = wrong_floyd(n, edges)
print(wrong_result[0][2])

这段错误代码的输出结果会是10，而不是正确的5。原因在于：当最内层循环遍历k时，每更新一次dist[i][j]，后续更大的k更新时，用到的dist[i][k]或者dist[k][j]可能已经被当前轮次更新过，也就是已经允许经过更大的k作为中间节点，相当于跳过了中间节点的顺序限制，导致状态转移不符合原本的定义，最终结果错误。

总结

Floyd-Warshall算法的循环顺序核心是保证状态依赖的正确性：中间节点k必须放在最外层，确保每一轮更新路径时，依赖的都是上一轮（不允许经过当前k）的距离数据。理解状态转移的依赖关系，就能明白为什么这个顺序不能改变，也能避免在实际编码中犯类似的错误。

另外如果需要判断图中是否存在负权回路，可以在Floyd-Warshall算法执行完成后，检查所有dist[i][i]的值，如果存在小于0的情况，就说明图中存在从节点i出发回到i的负权回路。

Floyd-Warshall算法循环顺序状态依赖性最短路径动态规划修改时间：2026-05-24 14:00:49