第45课：Floyd-Warshall 全源最短路径

学习目标

完成本课学习后，你将能够：

理解全源最短路径问题的概念和应用场景。
阐述 Floyd-Warshall 算法的核心思想（动态规划）。
实现 Floyd-Warshall 算法，并能解释代码中三层循环的含义。
分析算法的时间复杂度和空间复杂度，并了解其优缺点。

核心概念

什么是全源最短路径（All-Pairs Shortest Path）？

我们已经学习过 Dijkstra 和 Bellman-Ford 算法，它们都属于 单源最短路径（SSSP） 算法，即求解从一个源点到图中所有其他顶点的最短路径。

而 全源最短路径（APSP） 问题则更进一步：它要求找出图中 每一对顶点 (u, v) 之间的最短路径。一个朴素的想法是，对每个顶点都运行一次单源最短路径算法，但 Floyd-Warshall 算法提供了一种更优雅、更直接的解决方案。

Floyd-Warshall 算法：用“中转站”思维解题

Floyd-Warshall 算法基于 动态规划 的思想。它的核心逻辑可以通俗地理解为： “对于任意两点 i 和 j，考虑它们之间是否可以通过中间点 k 走一条更短的路。”

这个过程就像我们在现实生活中寻找路线：

初始状态：你知道所有相邻地点之间的直达距离（即邻接矩阵）。任何两点间的最短路径假设为直接相连（或无穷大）。
逐步放宽限制：算法会依次尝试将每一个顶点 k 作为“中转站”。
状态更新：对于每一对顶点 (i, j)，检查“从 i 先到 k，再从 k 到 j”这条新路径，是否比当前已知的从 i 到 j 的路径更短。如果更短，则更新 dist[i][j]。

用动态规划的语言来说，dist[i][j] 这个状态，在“允许经过前 k 个顶点作为中转”的条件下被不断更新。三层循环的核心逻辑就是这个状态转移过程。

算法特点：

适用性：可以处理 有向图 和 无向图，并且能够正确处理 负权边（但无法处理存在 负权环 的图，因为负权环会导致最短路径无限小）。
输出：算法结束后，我们得到的 dist 矩阵存储的就是任意两点间的最短路径长度。我们还可以通过 next 矩阵重建出具体的路径。

代码示例

以下是一个完整的 Python 实现。我们使用一个较大的数字（例如 float(‘inf’)）来表示两点间不直接相连。

def floyd_warshall(graph):
    """
    使用 Floyd-Warshall 算法计算图中所有顶点对之间的最短路径。
    
    参数:
        graph: 二维列表 (邻接矩阵)。graph[i][j] 表示从顶点 i 到顶点 j 的边的权重。
               如果不直接相连，则用一个很大的数 (如 INF) 表示。graph[i][i] 应为 0。
               
    返回:
        dist: 最短路径距离矩阵。dist[i][j] 是从 i 到 j 的最短路径长度。
        next_node: 路径重建矩阵。next_node[i][j] 存储从 i 到 j 最短路径上，i 的下一个顶点。
    """
    # 获取顶点数量
    n = len(graph)
    
    # 初始化距离矩阵 (dist) 和路径矩阵 (next_node)
    dist = [[float('inf')] * n for _ in range(n)]
    next_node = [[None] * n for _ in range(n)]
    
    # 初始化 dist 和 next_node
    for i in range(n):
        for j in range(n):
            # 初始距离就是图中的边权重
            dist[i][j] = graph[i][j]
            # 如果有直接相连的边 (i != j 且距离不是无穷大)，则路径上 i 的下一个节点是 j
            if i != j and graph[i][j] != float('inf'):
                next_node[i][j] = j
        # 顶点到自身的距离为 0
        dist[i][i] = 0
    
    # 核心算法：三重循环
    # k 代表“中转站”的顶点编号
    for k in range(n):
        # i 代表起点
        for i in range(n):
            # j 代表终点
            for j in range(n):
                # 松弛操作：如果经过顶点 k 的路径更短，则更新距离和路径
                # 条件：1) i->k 有路  2) k->j 有路  3) 新路径比旧路径短
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    # 更新路径：i->k 的下一个节点和 i->j 的下一个节点相同
                    next_node[i][j] = next_node[i][k]
    
    # 检测负权环：如果 dist 矩阵对角线出现负数，则存在负权环
    for i in range(n):
        if dist[i][i] < 0:
            print("警告：图中存在负权环，最短路径未定义。")
            return None, None
    
    return dist, next_node

def reconstruct_path(u, v, next_node):
    """
    根据 next_node 矩阵重建从 u 到 v 的具体路径。
    """
    if next_node[u][v] is None:
        return []
    path = [u]
    while u != v:
        u = next_node[u][v]
        path.append(u)
    return path

# 示例用法
if __name__ == "__main__":
    # 定义一个图的邻接矩阵 (4个顶点)
    # 0: inf, 3, inf, 7
    # 8, 0, 2, inf
    # 5, inf, 0, 1
    # 2, inf, inf, 0
    INF = float('inf')
    graph = [
        [0, 3, INF, 7],
        [8, 0, 2, INF],
        [5, INF, 0, 1],
        [2, INF, INF, 0]
    ]
    
    print("原始邻接矩阵:")
    for row in graph:
        print(row)
    
    dist_matrix, next_matrix = floyd_warshall(graph)
    
    if dist_matrix:
        print("\n所有顶点对之间的最短路径距离矩阵:")
        for i, row in enumerate(dist_matrix):
            print(f"从顶点 {i} 出发: {row}")
        
        # 测试路径重建：从顶点 0 到顶点 2
        u, v = 0, 2
        path = reconstruct_path(u, v, next_matrix)
        print(f"\n从顶点 {u} 到顶点 {v} 的最短路径: {' -> '.join(map(str, path))}")
        print(f"路径长度: {dist_matrix[u][v]}")

实践练习

练习 1（基础）：给定一个只有3个顶点（A=0, B=1, C=2）的有向图，其邻接矩阵如下：

[[0, 5, INF],
 [INF, 0, 2],
 [3, INF, 0]]

请手动模拟（或在代码中运行）Floyd-Warshall 算法的过程，写出当 k=1 时（即以顶点 B 为中转站），距离矩阵 dist 是如何更新的。

练习 2（进阶）：在提供的代码基础上，修改 floyd_warshall 函数，使其在算法执行过程中，当 dist[i][j] 被更新时，打印出一条信息，例如：“发现更短路径: 从 i 到 j 经由 k, 新长度为 X”。这有助于理解算法的执行流程。

练习 3（应用）：考虑一个小型计算机网络，其中每台计算机是一个顶点，它们之间的数据传输延迟（单位：毫秒）用边的权重表示。给定以下延迟矩阵（对角线为0）：

[[0, 10, 3, INF],
 [INF, 0, 1, 2],
 [INF, 4, 0, 8],
 [7, INF, INF, 0]]

使用你的代码计算所有计算机间的最短传输延迟。哪一对计算机之间的延迟最长？从计算机 0 到计算机 3 的最佳传输路径是什么？

常见错误

初始化错误：忘记将邻接矩阵中 graph[i][i] 初始化为 0，或者没有正确处理“不相连”（用 INF 表示）的情况。
循环顺序：三层循环的顺序必须是 k, i, j（中转点在最外层）。如果改成其他顺序，将无法实现动态规划的逐步放宽限制的过程，导致结果错误。
原地修改（In-place）陷阱：代码中的 dist 矩阵在循环中被不断更新。这是一个 原地算法，我们直接在原始矩阵上修改。要理解每次更新都会影响后续的计算。
忽略负权环：当图中存在负权环时，某些顶点对之间的“最短路径”会趋向于负无穷。代码中通过对角线检查来提示这一情况，但实际应用中需要特别注意输入图的合法性。
路径重建失误：在路径重建函数中，如果 next_node[u][v] 为 None，表示没有路径。在实现时，如果只考虑 u != v 的条件，可能会导致 u == v 时路径列表为空或出错，需要妥善处理。

小结

Floyd-Warshall 算法 解决的是 全源最短路径（APSP） 问题，即计算图中所有顶点对之间的最短路径。
其核心是 动态规划，通过三层循环（k, i, j）逐步尝试以每个顶点为中转站来更新路径。状态转移方程为：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。
算法的时间复杂度和空间复杂度均为 O(V³) 和 O(V²)，其中 V 是顶点数。这使得它适用于中等规模（几百个顶点）的图。
它可以正确处理带有 负权边 的图，但不能处理包含 负权环 的图。
通过维护一个额外的 next_node 矩阵，我们可以在 O(V) 时间内重建出任意两点间的具体最短路径。
与对每个点运行一次 Dijkstra（O(V * ElogV)）相比，Floyd-Warshall 在边数非常稠密（E ≈ V²）的图中更有优势，因为其复杂度与边数无关。

练习编辑器

rust