编写一个程序,要求找出给定无向图从A点到其他所有点的最短路径。要求输出A到各个点的最短路径的距离,格式如“A->A的最短路径为:A 长度:0”。
时间: 2023-06-26 15:08:20 浏览: 96
这个问题可以使用 Dijkstra 算法来解决。以下是 Python 代码实现:
```python
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph} # 初始距离为无穷大
distances[start] = 0 # 起始点距离为0
queue = [(0, start)]
while queue:
current_distance, current_node = heapq.heappop(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(queue, (distance, neighbor))
return distances
# 测试样例
graph = {
'A': {'B': 2, 'C': 4},
'B': {'C': 1, 'D': 3},
'C': {'D': 2},
'D': {}
}
distances = dijkstra(graph, 'A')
for node, distance in distances.items():
print(f"A->{node}的最短路径为:{node},长度为:{distance}")
```
输出结果为:
```
A->A的最短路径为:A,长度为:0
A->B的最短路径为:B,长度为:2
A->C的最短路径为:C,长度为:3
A->D的最短路径为:D,长度为:5
```
阅读全文