### Python 中实现最短路径算法的示例 #### Dijkstra 算法 Dijkstra 算法是一种用于计算加权图中单源最短路径的经典算法。以下是该算法的一个简单实现： ```python import heapq def dijkstra(graph, start): distances = {node: float('infinity') for node in graph} # 初始化所有节点的距离为无穷大 distances[start] = 0 # 起始节点距离设为0 priority_queue = [(0, start)] # 使用优先队列存储待处理节点及其当前已知最小距离 while priority_queue: current_distance, current_node = heapq.heappop(priority_queue) # 取出当前最小距离的节点 if current_distance > distances[current_node]: continue # 如果取出的距离大于记录中的距离，则跳过此节点 for neighbor, weight in graph[current_node].items(): # 遍历相邻节点 distance = current_distance + weight if distance < distances[neighbor]: # 更新更短的距离 distances[neighbor] = distance heapq.heappush(priority_queue, (distance, neighbor)) # 将更新后的邻居加入队列 return distances # 图表示（邻接表形式） graph = { 'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'C': 2, 'D': 5}, 'C': {'A': 4, 'B': 2, 'D': 1}, 'D': {'B': 5, 'C': 1} } print(dijkstra(graph, 'A')) # 输出从 A 到其他各点的最短距离 ``` 以上代码实现了 Dijkstra 算法，适用于带非负权重的有向或无向图[^1]。 --- #### BFS 最短路径算法 当图中所有的边权重均为 1 时，可以使用广度优先搜索（BFS）来求解最短路径问题。以下是一个简单的 BFS 实现： ```python from collections import deque def bfs_shortest_path(graph, start, goal): queue = deque([(start, [start])]) # 队列初始化为起点以及其路径列表 visited = set() # 访问过的节点集合 while queue: current_node, path = queue.popleft() if current_node == goal: return path # 找到目标节点返回路径 if current_node not in visited: visited.add(current_node) for neighbor in graph.get(current_node, []): # 获取当前节点的所有邻居 if neighbor not in visited: queue.append((neighbor, path + [neighbor])) # 添加新的路径 return None # 若未找到路径则返回 None # 图表示（邻接表形式） graph = { 'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'D'], 'D': ['B', 'C'] } result = bfs_shortest_path(graph, 'A', 'D') if result: print(f"BFS Shortest Path from A to D is {result}") # 输出最短路径 else: print("No path found.") ``` 这段代码展示了如何通过 BFS 寻找两个节点之间的最短路径，前提是每条边的权重相同且为 1[^2]。 --- #### 总结 - 当图中存在不同权重时，推荐使用 **Dijkstra** 或者 **SPFA** 算法。 - 对于单位权重的情况，可以直接采用 **BFS** 来高效解决问题。