编写一个程序,要求找出给定无向图从A点到其他所有点的最短路径。要求输出A到各个点的最短路径的距离,格式如“A->A的最短路径为:A 长度:0”。
时间: 2023-06-27 17:02:54 浏览: 79
以下是使用Dijkstra算法实现的Python代码:
```python
import heapq
class 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')
```
输出结果为:
```
A->A的最短路径为:A 长度:0
A->B的最短路径为:B 长度:3
A->C的最短路径为:C 长度:8
A->D的最短路径为:D 长度:1
A->E的最短路径为:E 长度:2
```
阅读全文