### Dijkstra 和 BFS 的 Python 实现 #### 使用 BFS 计算无权图中的最短路径 如果给定的图是无权图，则可以使用广度优先搜索 (BFS) 来计算从顶点 A 到 O 的最短路径及其长度。以下是基于 BFS 的实现： ```python from collections import deque, defaultdict def bfs(graph, start, goal): queue = deque([(start, [start])]) visited = set() while queue: current_vertex, path = queue.popleft() if current_vertex not in visited: visited.add(current_vertex) if current_vertex == goal: return path, len(path) - 1 for neighbor in graph[current_vertex]: if neighbor not in visited: queue.append((neighbor, path + [neighbor])) return None, float('inf') # 定义一个简单的无权图作为邻接表 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F', 'G'], 'F': ['C', 'E', 'H'], 'G': ['E', 'H', 'I'], 'H': ['F', 'G', 'O'], 'I': ['G', 'O'], 'O': ['H', 'I'] } path_bfs, length_bfs = bfs(graph, 'A', 'O') if path_bfs is not None: print(f"BFS 最短路径: {path_bfs}, 长度: {length_bfs}") else: print("未找到路径") ``` 此代码实现了 BFS 并返回从起点 `A` 到终点 `O` 的最短路径以及其长度[^4]。 --- #### 使用 Dijkstra 算法计算加权图中的最短路径 如果图是有权图，则应使用 Dijkstra 算法来计算从顶点 A 到 O 的最短路径及其长度。以下是基于 Dijkstra 的实现： ```python import heapq def dijkstra(graph, start, goal): pq = [] # 优先队列 heapq.heappush(pq, (0, start)) distances = {vertex: float('infinity') for vertex in graph} previous_vertices = {vertex: None for vertex in graph} distances[start] = 0 while pq: current_distance, current_vertex = heapq.heappop(pq) if current_distance > distances[current_vertex]: continue if current_vertex == goal: break for neighbor, weight in graph[current_vertex].items(): distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance previous_vertices[neighbor] = current_vertex heapq.heappush(pq, (distance, neighbor)) path, current_vertex = [], goal while previous_vertices[current_vertex] is not None: path.insert(0, current_vertex) current_vertex = previous_vertices[current_vertex] if path and current_vertex == start: path.insert(0, start) return path, distances[goal] # 定义一个带权重的有向图作为邻接表 weighted_graph = { 'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'D': 2, 'E': 7}, 'C': {'A': 4, 'F': 3}, 'D': {'B': 2}, 'E': {'B': 7, 'F': 1, 'G': 5}, 'F': {'C': 3, 'E': 1, 'H': 8}, 'G': {'E': 5, 'H': 6, 'I': 9}, 'H': {'F': 8, 'G': 6, 'O': 2}, 'I': {'G': 9, 'O': 4}, 'O': {} } path_dijkstra, length_dijkstra = dijkstra(weighted_graph, 'A', 'O') print(f"Dijkstra 最短路径: {path_dijkstra}, 长度: {length_dijkstra}") ``` 这段代码通过维护最小堆的方式逐步扩展当前已知的最短路径，最终得到从起点 `A` 到目标点 `O` 的最短路径及其总权重[^2]。 --- ### 结果分析 - 如果输入的是 **无权图**，则推荐使用 BFS 方法，因为它的时间复杂度较低且易于理解。 - 如果输入的是 **有权图**，尤其是存在不同边权重的情况下，则需采用 Dijkstra 算法以获得精确的结果。 以上两种方法均适用于不同的场景需求，并能有效解决问题[^3]。 ---