用Python编写一个程序,要求找出给定无向图从A点到其他所有点的最短路径。要求输出A到各个点的最短路径的距离,格式如“A->A的最短路径为:A 长度:0”。
时间: 2023-06-27 10:02:28 浏览: 165
下面是一个使用Dijkstra算法实现的Python程序,可以找出给定无向图从A点到其他所有点的最短路径。
```python
import heapq
# 无穷大表示两点之间没有直接连接
INF = float('inf')
# 无向图的邻接矩阵表示
graph = [[0, 2, 1, INF],
[2, 0, INF, 1],
[1, INF, 0, 1],
[INF, 1, 1, 0]]
# 起点A
start = 0
# 存储起点A到其他点的最短路径长度
distances = [INF] * len(graph)
distances[start] = 0
# 使用堆优化的Dijkstra算法寻找最短路径
queue = [(0, start)]
while queue:
(cost, node) = heapq.heappop(queue)
if cost > distances[node]:
continue
for neighbor, weight in enumerate(graph[node]):
if weight != INF and distances[node] + weight < distances[neighbor]:
distances[neighbor] = distances[node] + weight
heapq.heappush(queue, (distances[neighbor], neighbor))
# 输出结果
for i, distance in enumerate(distances):
print(f"A->{i}的最短路径为:{i} 长度:{distance}")
```
输出结果如下:
```
A->0的最短路径为:0 长度:0
A->1的最短路径为:1 长度:2
A->2的最短路径为:2 长度:1
A->3的最短路径为:3 长度:2
```
其中,第一行表示从A点到自己的最短路径长度为0,其他行表示从A点到其他点的最短路径长度。
阅读全文