使用Dijkstra算法,对给定的图计算出两点间的最短路径
时间: 2023-11-30 15:43:17 浏览: 45
以下是使用Dijkstra算法,对给定的图计算出两点间的最短路径的步骤和示例代码:
1. 确定起点和终点,以及图的邻接矩阵表示。
2. 初始化距离数组dist和标记数组visited,将起点到自身的距离设为0,其他点到起点的距离设为无穷大,标记数组visited中所有元素都为False。
3. 对于起点到所有邻接点的距离,更新距离数组dist和标记数组visited。
4. 从未标记的节点中选择距离起点最近的节点,将其标记为已访问,并更新其邻接点到起点的距离。
5. 重复步骤4,直到终点被标记为已访问或者所有未标记的节点到起点的距离都为无穷大。
6. 根据距离数组dist,回溯出起点到终点的最短路径。
示例代码如下:
```python
import sys
# 邻接矩阵表示图
graph = [[0, 10, sys.maxsize, sys.maxsize, sys.maxsize],
[10, 0, 50, sys.maxsize, 30],
[sys.maxsize, 50, 0, 20, 40],
[sys.maxsize, sys.maxsize, 20, 0, 60],
[sys.maxsize, 30, 40, 60, 0]]
# Dijkstra算法求最短路径
def dijkstra(graph, start, end):
n = len(graph)
dist = [sys.maxsize] * n
visited = [False] * n
dist[start] = 0
for i in range(n):
min_dist = sys.maxsize
min_index = -1
for j in range(n):
if not visited[j] and dist[j] < min_dist:
min_dist = dist[j]
min_index = j
if min_index == -1:
break
visited[min_index] = True
for j in range(n):
if not visited[j] and graph[min_index][j] != sys.maxsize:
new_dist = dist[min_index] + graph[min_index][j]
if new_dist < dist[j]:
dist[j] = new_dist
path = []
cur = end
while cur != start:
path.append(cur)
for i in range(n):
if graph[i][cur] != sys.maxsize and dist[cur] == dist[i] + graph[i][cur]:
cur = i
break
path.append(start)
return list(reversed(path)), dist[end]
# 测试
start = 0
end = 4
path, dist = dijkstra(graph, start, end)
print("从{}到{}的最短路径为:{}".format(start, end, path))
print("最短距离为:{}".format(dist))
```