迪杰斯特拉算法的具体步骤是什么?
时间: 2023-12-30 10:23:48 浏览: 54
迪杰斯特拉算法的具体步骤如下:
1. 初始化:创建一个空集合S,用于存放已经找到最短路径的顶点;创建一个距离数组dist,用于存放起始点到各个顶点的最短路径长度;创建一个前驱数组prev,用于存放最短路径上每个顶点的前驱顶点。
2. 将起始点加入集合S,并将起始点的距离设为0。
3. 对于起始点的所有邻接顶点,更新其距离数组dist和前驱数组prev。如果通过起始点到达邻接顶点的路径长度小于dist中的值,则更新dist和prev。
4. 从剩余的顶点中选择一个距离最小的顶点k,将其加入集合S。
5. 对于顶点k的所有邻接顶点,更新其距离数组dist和前驱数组prev。如果通过顶点k到达邻接顶点的路径长度小于dist中的值,则更新dist和prev。
6. 重复步骤4和步骤5,直到所有顶点都加入集合S。
7. 根据前驱数组prev,可以得到起始点到其他顶点的最短路径。
以下是一个示例代码:
```python
import sys
def dijkstra(graph, start):
# 初始化
S = set()
dist = {v: sys.maxsize for v in graph}
prev = {v: None for v in graph}
# 将起始点加入集合S,并将起始点的距离设为0
S.add(start)
dist[start] = 0
# 更新起始点的邻接顶点的距离数组dist和前驱数组prev
for v in graph[start]:
dist[v] = graph[start][v]
prev[v] = start
while len(S) < len(graph):
# 选择一个距离最小的顶点k,将其加入集合S
k = min((v for v in graph if v not in S), key=lambda x: dist[x])
S.add(k)
# 更新顶点k的邻接顶点的距离数组dist和前驱数组prev
for v in graph[k]:
if v not in S and dist[k] + graph[k][v] < dist[v]:
dist[v] = dist[k] + graph[k][v]
prev[v] = k
return dist, prev
# 示例图的邻接表表示
graph = {
'A': {'B': 5, 'C': 1},
'B': {'A': 5, 'C': 2, 'D': 1},
'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
'E': {'C': 8, 'D': 3},
'F': {'D': 6}
}
start = 'A'
dist, prev = dijkstra(graph, start)
print("起始点到各个顶点的最短路径长度:", dist)
print("最短路径上每个顶点的前驱顶点:", prev)
```
阅读全文