LeetCode Floyd-Warshall 算法题解

LeetCode Floyd-Warshall 算法题解题目描述Floyd-Warshall 算法是一种用于解决所有节点对之间最短路径问题的动态规划算法。它可以处理带有负权边的图但不能处理带有负权环的图。示例对于以下加权图A --(2)-- B --(4)-- C | | | (1) (-3) (1) | | | D --(5)-- E --(2)-- F所有节点对之间的最短路径长度为A → B: 2A → D: 1A → E: -1A → C: 6A → F: 1B → A: 2B → E: -3B → C: 4B → F: -1等等...解题思路方法Floyd-Warshall 算法思路Floyd-Warshall 算法的核心思想是使用动态规划通过中间节点来更新任意两个节点之间的最短路径。具体步骤初始化一个距离矩阵其中 dist[i][j] 表示从节点 i 到节点 j 的直接距离。对于每个中间节点 k检查是否通过 k 可以得到更短的路径如果 dist[i][k] dist[k][j] dist[i][j]则更新 dist[i][j]。重复步骤 2直到所有中间节点都被考虑。复杂度分析时间复杂度O(V³)其中 V 是顶点数。需要三重循环来遍历所有节点对和中间节点。空间复杂度O(V²)需要存储距离矩阵。代码实现方法Floyd-Warshall 算法# Floyd-Warshall 算法 def floyd_warshall(graph): # 获取所有节点并排序以便使用索引 nodes sorted(graph.keys()) n len(nodes) # 创建节点到索引的映射 node_to_idx {node: i for i, node in enumerate(nodes)} # 初始化距离矩阵源节点到自身的距离为 0其他为无穷大 INF float(infinity) dist [[INF] * n for _ in range(n)] for i in range(n): dist[i][i] 0 # 填充初始距离 for u in graph: u_idx node_to_idx[u] for v, weight in graph[u].items(): v_idx node_to_idx[v] dist[u_idx][v_idx] weight # Floyd-Warshall 算法核心 for k in range(n): for i in range(n): 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] # 检查是否存在负权环 has_negative_cycle False for i in range(n): if dist[i][i] 0: has_negative_cycle True break # 将距离矩阵转换回节点形式 result {} for i in range(n): u nodes[i] result[u] {} for j in range(n): v nodes[j] result[u][v] dist[i][j] return result, has_negative_cycle # 测试 def test_floyd_warshall(): # 构建图结构邻接表 graph { A: {B: 2, D: 1}, B: {A: 2, C: 4, E: -3}, C: {B: 4, F: 1}, D: {A: 1, E: 5}, E: {B: -3, D: 5, F: 2}, F: {C: 1, E: 2} } # 测试所有节点对之间的最短路径 print(All-pairs shortest paths:) distances, has_negative_cycle floyd_warshall(graph) for u in distances: for v in distances[u]: print(f{u} → {v}: {distances[u][v]}) print(fHas negative cycle: {has_negative_cycle}) if __name__ __main__: test_floyd_warshall()测试用例测试用例所有节点对之间的最短路径输入A --(2)-- B --(4)-- C | | | (1) (-3) (1) | | | D --(5)-- E --(2)-- F输出All-pairs shortest paths: A → A: 0 A → B: 2 A → C: 6 A → D: 1 A → E: -1 A → F: 1 B → A: 2 B → B: 0 B → C: 4 B → D: 3 B → E: -3 B → F: -1 C → A: 7 C → B: 6 C → C: 0 C → D: 8 C → E: 3 C → F: 1 D → A: 1 D → B: 3 D → C: 7 D → D: 0 D → E: 2 D → F: 4 E → A: 5 E → B: -3 E → C: 1 E → D: 5 E → E: 0 E → F: 2 F → A: 8 F → B: 3 F → C: 1 F → D: 8 F → E: 2 F → F: 0 Has negative cycle: False总结Floyd-Warshall 算法是一种重要的图论算法它可以用于解决所有节点对之间的最短路径问题。通过动态规划和中间节点的概念Floyd-Warshall 算法可以高效地计算出所有节点对之间的最短路径。Floyd-Warshall 算法的核心思想是通过中间节点来更新任意两个节点之间的最短路径。掌握 Floyd-Warshall 算法的原理和实现对于理解和解决图论相关问题非常重要。