Floyd-Warshall 算法求解所有顶点对最短路径

题目描述

给定一个带权有向图（或带权无向图），图中可能包含负权边，但不能包含负权环。要求计算图中所有顶点对之间的最短路径长度。具体来说，对于图中的每一对顶点 (i, j)，我们需要输出从顶点 i 到顶点 j 的最短路径的权值（距离）。

解题思路

Floyd-Warshall 算法是一种动态规划算法，其核心思想是：对于图中的所有顶点，逐步考虑它们是否可以作为中间顶点来改进已知的最短路径。算法的核心是一个三维（但通常优化为二维）的动态规划数组 dist[k][i][j]，表示“只允许使用顶点 0, 1, ..., k 作为中间顶点时，从顶点 i 到顶点 j 的最短路径长度”。通过逐步增加 k 的值，最终得到任意两个顶点之间的最短路径。

详细步骤

假设图有 n 个顶点，编号为 0 到 n-1。图的权值用一个 n×n 的矩阵 W 表示，其中 W[i][j] 表示从顶点 i 到顶点 j 的边的权值。如果 i 到 j 没有直接相连的边，则设 W[i][j] = ∞（一个很大的数，如 10^9）。对于所有 i，设 W[i][i] = 0。

步骤 1：初始化距离矩阵

创建一个 n×n 的二维数组 dist，初始时 dist[i][j] = W[i][j]。这个 dist 矩阵就是当不允许使用任何中间顶点（k = -1）时的最短路径估计。此时，dist[i][j] 就是边 (i, j) 的权值（如果存在直接边），否则为 ∞。

步骤 2：动态规划递推

对于每个中间顶点 k（从 0 到 n-1），我们尝试用 k 来改进所有顶点对 (i, j) 之间的最短路径。递推公式如下：
如果 dist[i][k] + dist[k][j] < dist[i][j]，则更新 dist[i][j] = dist[i][k] + dist[k][j]。
这个公式的含义是：如果从 i 到 j 经过顶点 k 的路径比当前已知的路径更短，就更新最短路径。

为什么这样是正确的？

• 当考虑中间顶点 k 时，我们已经计算了只允许使用顶点 0, 1, ..., k-1 作为中间顶点时所有顶点对的最短路径。
• 因此，dist[i][k] 和 dist[k][j] 已经是基于前 k-1 个中间顶点的最短路径。
• 所以，经过 k 的路径 dist[i][k] + dist[k][j] 可能是从 i 到 j 的更短路径。

步骤 3：执行三层循环

外层循环遍历所有可能的中间顶点 k（0 到 n-1）。
内两层循环遍历所有顶点对 (i, j)（0 到 n-1），并应用上述递推公式更新 dist[i][j]。
注意：这个算法允许顶点 i、j、k 相同，但 i 和 j 相同时距离为 0，不会更新；k 与 i 或 j 相同时，递推公式依然成立（例如，如果 k = i，则 dist[i][k] = 0，所以 dist[i][k] + dist[k][j] = dist[i][j]，不会改变）。

步骤 4：检测负权环

在算法结束后，检查 dist 矩阵的主对角线元素（即 dist[i][i]）。如果存在某个 i 使得 dist[i][i] < 0，则说明图中存在负权环（因为从一个顶点到自身的最短路径应该是 0，除非经过负权环可以更“短”）。

步骤 5：输出结果

最终 dist[i][j] 就是从顶点 i 到顶点 j 的最短路径长度。如果 dist[i][j] 仍然为 ∞，则表示从 i 到 j 不可达。

举例说明

考虑一个简单有向图，顶点数为 3，权重矩阵 W 如下（∞ 表示无穷大）：

W = [
    [0, 3, ∞],
    [∞, 0, 1],
    [4, ∞, 0]
]

• 初始化 dist = W。
• k=0（中间顶点为 0）：
  • 检查所有 (i, j)：dist[2][1] 可以通过 k=0 改进吗？dist[2][0] + dist[0][1] = 4 + 3 = 7，当前 dist[2][1] = ∞，所以更新 dist[2][1] = 7。
  • 其他元素不变。
• k=1（中间顶点为 1）：
  • dist[0][2]：dist[0][1] + dist[1][2] = 3 + 1 = 4，当前 dist[0][2] = ∞，更新为 4。
  • dist[2][2]：dist[2][1] + dist[1][2] = 7 + 1 = 8，当前 dist[2][2] = 0，不更新（因为 8 > 0）。
• k=2（中间顶点为 2）：
  • dist[1][0]：dist[1][2] + dist[2][0] = 1 + 4 = 5，当前 dist[1][0] = ∞，更新为 5。
  • dist[1][1]：dist[1][2] + dist[2][1] = 1 + 7 = 8，当前 dist[1][1] = 0，不更新。
  • dist[0][0]：dist[0][2] + dist[2][0] = 4 + 4 = 8，不更新。
    最终 dist 矩阵为：

[
    [0, 3, 4],
    [5, 0, 1],
    [4, 7, 0]
]

所有顶点对的最短路径已计算完成。

时间复杂度和空间复杂度

• 时间复杂度：O(n³)，因为三层嵌套循环，每层最多 n 次迭代。
• 空间复杂度：O(n²)，只需要存储 n×n 的距离矩阵。

算法优缺点

优点：

1. 代码简单，易于实现。
2. 可以处理负权边。
3. 可以一次性求出所有顶点对之间的最短路径。

缺点：

1. 时间复杂度较高，不适合顶点数很多的大规模图（通常 n ≤ 500 时可用）。
2. 不能处理负权环（但可以检测到）。

代码模板（Python 实现）

def floyd_warshall(graph):
    n = len(graph)
    dist = [[graph[i][j] for j in range(n)] for i in range(n)]
    
    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]
    
    # 检测负权环
    for i in range(n):
        if dist[i][i] < 0:
            print("图中存在负权环")
            return None
    
    return dist

总结：Floyd-Warshall 算法通过动态规划逐步引入中间顶点来优化所有顶点对之间的最短路径，虽然时间复杂度较高，但其简洁性和处理负权边的能力使其成为小规模图全源最短路径问题的常用解法。