import heapqclass Graph: def __init__(self, vertices): self.vertices = vertices self.adjacency_list = {v: [] for v in vertices} def add_edge(self, u, v, weight): self.adjacency_list[u].append((v, weight)) self.adjacency_list[v].append((u, weight)) def dijkstra(self, source): heap = [(0, source)] visited = set() shortest_distances = {v: float('inf') for v in self.vertices} shortest_distances[source] = 0 while heap: (dist, current_vertex) = heapq.heappop(heap) if current_vertex in visited: continue visited.add(current_vertex) for (neighbor, weight) in self.adjacency_list[current_vertex]: distance = dist + weight if distance < shortest_distances[neighbor]: shortest_distances[neighbor] = distance heapq.heappush(heap, (distance, neighbor)) for v in self.vertices: print(f"{source}->{v}的最短路径为：{v} 长度：{shortest_distances[v]}")# 测试代码vertices = ['A', 'B', 'C', 'D', 'E']graph = Graph(vertices)graph.add_edge('A', 'B', 6)graph.add_edge('A', 'D', 1)graph.add_edge('B', 'C', 5)graph.add_edge('B', 'D', 2)graph.add_edge('B', 'E', 2)graph.add_edge('C', 'E', 5)graph.add_edge('D', 'E', 1)graph.dijkstra('A')

这是一个使用 Dijkstra 算法求解最短路径的代码。假设有一个无向图，使用字典 `adjacency_list` 存储每个顶点的邻接表。在 `dijkstra` 方法中，首先将起始顶点放入堆中，然后使用 `visited` 集合记录已经访问过的顶点。使用字典 `shortest_distances` 记录每个顶点到起始顶点的最短距离，初始值为正无穷。当从堆中弹出一个顶点时，如果该顶点已经被访问过，则直接跳过。否则遍历该顶点的所有邻居，计算它们到起始顶点的距离，并更新 `shortest_distances` 和堆。最后，打印出起始顶点到每个顶点的最短路径长度。

代码中给出了一个简单的测试例子，使用节点 A、B、C、D、E 构建一个无向图，并从起点 A 开始求解最短路径。