详细描述Dijkstra算法
时间: 2024-03-31 07:30:59 浏览: 16
Dijkstra算法是一种解决带权重的有向图上单源最短路径问题的算法[^2]。它要求所有边的权重都为非负值。以下是Dijkstra算法的详细描述:
1. 创建一个空的距离字典dist,用于存储从起始节点到其他节点的最短距离。将起始节点的距离设置为0,其他节点的距离设置为无穷大。
2. 创建一个空的已访问集合visited,用于存储已经找到最短路径的节点。
3. 重复以下步骤,直到所有节点都被访问:
- 从未访问的节点中选择距离起始节点最近的节点,将其标记为当前节点。
- 将当前节点添加到visited集合中。
- 更新当前节点的邻居节点的最短距离:
- 遍历当前节点的所有邻居节点。
- 计算从起始节点经过当前节点到邻居节点的距离。
- 如果该距离小于邻居节点当前的最短距离,则更新邻居节点的最短距离为该距离。
4. 当所有节点都被访问后,dist字典中存储的就是从起始节点到其他节点的最短距离。
下面是一个使用Dijkstra算法求解最短路径的示例代码:
```python
def dijkstra(graph, start):
# 初始化距离字典
dist = {node: float('inf') for node in graph}
dist[start] = 0
# 初始化已访问集合
visited = set()
while len(visited) < len(graph):
# 选择距离起始节点最近的节点
current_node = min((node for node in graph if node not in visited), key=lambda x: dist[x])
# 将当前节点添加到已访问集合中
visited.add(current_node)
# 更新邻居节点的最短距离
for neighbor in graph[current_node]:
distance = dist[current_node] + graph[current_node][neighbor]
if distance < dist[neighbor]:
dist[neighbor] = distance
return dist
```