### Python 实现最短路径算法 以下是基于 Dijkstra 算法、Floyd-Warshall 算法以及 SPFA 算法的 Python 示例代码。 #### 1. Dijkstra 算法 Dijkstra 算法适用于单源最短路径问题，能够高效地找到从起点到其他节点的最短路径[^2]。下面是一个完整的实现： ```python import heapq def dijkstra(graph, start): n = len(graph) dist = [float('inf')] * n dist[start] = 0 heap = [(0, start)] while heap: current_dist, u = heapq.heappop(heap) if current_dist > dist[u]: continue for v, weight in graph[u]: distance = current_dist + weight if distance < dist[v]: dist[v] = distance heapq.heappush(heap, (distance, v)) return dist # 测试用例 graph = [ [(1, 7), (2, 9), (5, 14)], [(0, 7), (2, 10), (3, 15)], [(0, 9), (1, 10), (3, 11), (4, 2)], [(1, 15), (2, 11), (4, 6)], [(2, 2), (3, 6), (5, 9)], [(0, 14), (4, 9)] ] print(dijkstra(graph, 0)) # 输出从顶点0到其余各点的最短距离 ``` --- #### 2. Floyd-Warshall 算法 Floyd-Warshall 算法用于解决多源最短路径问题，适合于稠密图或需要全局最优解的情况[^4]。下面是其实现： ```python def floyd_warshall(graph): n = len(graph) dist = [[float('inf')] * n for _ in range(n)] # 初始化邻接矩阵 for i in range(n): for j in range(n): if i == j: dist[i][j] = 0 elif graph[i][j] != float('inf'): dist[i][j] = graph[i][j] # 动态规划更新最短路径 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] return dist # 测试用例 INF = float('inf') graph = [ [0, 7, INF, INF], [INF, 0, 10, 15], [INF, INF, 0, 11], [INF, INF, INF, 0] ] result = floyd_warshall(graph) for row in result: print(row) # 打印每一对顶点之间的最短距离 ``` --- #### 3. SPFA 算法 SPFA（Shortest Path Faster Algorithm）是对 Bellman-Ford 的改进版本，特别适合稀疏图中的单源最短路径问题[^3]。以下是其代码实现： ```python from collections import deque def spfa(graph, start): n = len(graph) dist = [float('inf')] * n dist[start] = 0 queue = deque([start]) in_queue = [False] * n in_queue[start] = True while queue: u = queue.popleft() in_queue[u] = False for v, weight in graph[u]: new_distance = dist[u] + weight if new_distance < dist[v]: dist[v] = new_distance if not in_queue[v]: queue.append(v) in_queue[v] = True return dist # 测试用例 graph = [ [(1, 2), (2, 6)], [(2, 3), (3, 8)], [(3, 5)], [], [] ] print(spfa(graph, 0)) # 输出从顶点0到其余各点的最短距离 ``` --- ### 总结 上述三种算法各有优劣： - **Dijkstra** 适用于加权正数边的单源最短路径问题，效率较高但不支持负权重边。 - **Floyd-Warshall** 能够处理任意两点间的所有最短路径，尤其适合小型密集图。 - **SPFA** 则是针对稀疏图设计的更快速解决方案，能有效应对负权重边的存在。