Floyd算法（又称Floyd-Warshall算法）的Python源代码实现如下。该算法用于计算**加权图中所有顶点对之间的最短路径**，是一种基于**动态规划**的经典算法 [ref_1][ref_2]。 以下是最核心的算法实现，它接受一个表示图的邻接矩阵作为输入，并直接在该矩阵上更新为所有点对的最短距离矩阵。 ```python def floyd_warshall(graph): """ 使用Floyd-Warshall算法计算所有顶点对之间的最短路径。 参数: graph: 二维列表，表示图的邻接矩阵。 graph[i][j] 表示顶点 i 到顶点 j 的距离。 如果 i 和 j 不直接相连，则用一个大数（如 float('inf')）表示。 对角线 graph[i][i] 应为 0。 返回: dist: 二维列表，dist[i][j] 表示顶点 i 到顶点 j 的最短距离。 """ # 获取图中顶点的数量 n = len(graph) # 创建距离矩阵的副本，避免修改原图 dist = [row[:] for row in graph] # 三重循环，核心动态规划过程 for k in range(n): # 中间顶点 for i in range(n): # 起点 for j in range(n): # 终点 # 如果通过顶点 k 的路径比已知的直接路径更短，则更新最短距离 if dist[i][k] != float('inf') and dist[k][j] != float('inf'): if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist ``` ### 算法详解与步骤说明 Floyd算法的核心思想是动态规划，其状态转移方程为：`dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`。它通过逐步“允许”将每个顶点作为中转站，来不断优化任意两点间的距离估计 [ref_2][ref_4]。 完整的实现通常还包括**路径记录**功能和易于测试的**示例**。下表对比了基础版本与增强版本的功能差异： | 特性 | 基础版本（仅距离） | 增强版本（含路径回溯） | | :--- | :--- | :--- | | **输出** | 最短距离矩阵 | 最短距离矩阵 + 路径前驱矩阵 | | **空间复杂度** | O(V²) | O(V²) | | **主要用途** | 仅需最短距离时 | 需要还原具体路径时 | 以下代码展示了包含路径记录功能的完整实现和示例 [ref_4][ref_6]。 ```python def floyd_warshall_with_path(graph): """ Floyd算法完整实现，包含最短路径的记录。 参数: graph: 邻接矩阵。 返回: dist: 最短距离矩阵。 next_node: 路径矩阵，next_node[i][j]表示从i到j的最短路径上，i之后的第一個顶点。 """ n = len(graph) dist = [row[:] for row in graph] # 初始化路径矩阵。如果i和j直接相连或i==j，则下一个节点是j，否则为None。 next_node = [[None] * n for _ in range(n)] for i in range(n): for j in range(n): if i == j or graph[i][j] == float('inf'): next_node[i][j] = None else: next_node[i][j] = j # 动态规划核心过程 for k in range(n): for i in range(n): # 可选优化：如果dist[i][k]为无穷大，则可跳过对j的循环 if dist[i][k] == float('inf'): continue for j in range(n): # 如果通过k点的路径更短 new_dist = dist[i][k] + dist[k][j] if new_dist < dist[i][j]: dist[i][j] = new_dist # 关键：更新路径，从i到j的新路径的第一站，是从i到k路径的第一站 next_node[i][j] = next_node[i][k] return dist, next_node def reconstruct_path(start, end, next_node): """ 利用next_node矩阵重建从start到end的具体路径。 参数: start: 起点索引。 end: 终点索引。 next_node: 路径矩阵。 返回: path: 从起点到终点的顶点索引列表。如果不可达，返回空列表。 """ if next_node[start][end] is None: return [] path = [start] while start != end: start = next_node[start][end] path.append(start) return path # ==================== 使用示例 ==================== if __name__ == "__main__": # 定义一个示例图（4个顶点）的邻接矩阵 # 我们用 INF 表示两个顶点之间没有直接边 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 = floyd_warshall(graph) print("\n计算后的最短距离矩阵（基础版本）：") for row in dist_matrix: # 将 INF 输出为特定符号便于阅读 print([int(d) if d != INF else "INF" for d in row]) # 调用完整算法（含路径记录） dist, next_node = floyd_warshall_with_path(graph) print("\n计算后的最短距离矩阵（完整版本）：") for row in dist: print([int(d) if d != INF else "INF" for d in row]) # 测试路径重建 start_vertex = 0 end_vertex = 3 path = reconstruct_path(start_vertex, end_vertex, next_node) print(f"\n从顶点 {start_vertex} 到顶点 {end_vertex} 的最短路径是：{path}") print(f"路径距离为：{dist[start_vertex][end_vertex]}") # 验证所有顶点对 print("\n所有顶点对的最短路径：") n = len(graph) for i in range(n): for j in range(n): if i != j: p = reconstruct_path(i, j, next_node) if p: print(f"{i} -> {j}: {p}, 距离={dist[i][j]}") else: print(f"{i} -> {j}: 不可达") ``` ### 算法关键点与应用场景分析 1. **时间复杂度**：三层嵌套循环导致时间复杂度为 **O(V³)**，其中 V 是顶点数。因此它适用于顶点规模不太大（通常 V < 500）的稠密图 [ref_3]。 2. **空间复杂度**：使用邻接矩阵，空间复杂度为 **O(V²)**。路径记录矩阵 `next_node` 也占用 O(V²) 空间。 3. **核心优势**：代码极其简洁，能够一次性求出所有点对的最短路径，特别适合需要**频繁查询任意两点最短距离**的场景 [ref_1]。 4. **与Dijkstra算法的对比**：Dijkstra算法是单源最短路径算法，时间复杂度为 O(E log V)（使用优先队列）。如果需要计算图中所有点对的最短路径，对每个顶点运行一次Dijkstra算法的总复杂度是 O(V * E log V)。对于稠密图（E ≈ V²），Floyd算法的 O(V³) 可能更具竞争力，且实现更简单；对于稀疏图，多次Dijkstra算法通常更快 [ref_3]。 5. **负权边处理**：Floyd算法可以处理带有**负权边**的图，但**不能处理包含负权环**的图。如果图中存在负权环，则某些顶点对之间不存在最短路径（可以通过不断绕环使距离趋于负无穷），算法无法给出有效结果 [ref_2]。 6. **动态规划本质**：最外层的循环变量 `k` 代表“允许使用的前 k 个顶点作为中转站”。算法结束时，`dist` 矩阵中便包含了允许使用所有顶点作为中转时的最短距离 [ref_4]。 ### 典型应用场景示例 一个典型的应用是**校园导航系统** [ref_5]。系统将校园内的地点（如教学楼、图书馆、食堂）抽象为图的顶点，将道路抽象为边，边的权重可以是实际距离或步行时间。系统初始化时，使用Floyd算法一次性计算出所有地点之间的最短路径并存储。当用户查询任意两个地点间的路线时，系统可以在 O(1) 时间内从 `dist` 矩阵中取出距离，并通过 `next_node` 矩阵在 O(L)（L为路径长度）时间内快速重建具体路径，从而实现高效的实时导航。