迪杰斯特拉算法代码呈现
时间: 2024-05-13 12:11:59 浏览: 17
Dijkstra算法是一种用于解决带权重图的单源最短路径问题的贪心算法。该算法维护一个集合,其中包含从源节点到其余所有节点的最短路径的估计值。
以下是Dijkstra算法的基本思路:
1. 初始化:将起始节点标记为已访问,将起始节点到自身的距离设置为0,将起始节点到其他所有节点的距离设置为无穷大。
2. 迭代:对于未访问的节点,找到到起始节点距离最短的节点,并将其标记为已访问。对于该节点的每个相邻节点,更新其到起始节点的距离(如果该距离比之前计算的估计值更小)。
3. 终止条件:当所有节点都被访问时,算法结束。
以下是Dijkstra算法的Python代码实现:
```python
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph} # 初始化距离估计值为无穷大
distances[start] = 0 # 起始节点到自身的距离为0
pq = [(0, start)] # 用堆来存储未访问的节点
while pq:
(dist, node) = heapq.heappop(pq) # 找到当前未访问节点中距离最短的节点
if dist > distances[node]:
continue # 如果当前距离估计值已经被更新,则忽略该节点
for neighbor in graph[node]: # 更新当前节点的相邻节点的距离估计值
new_dist = distances[node] + graph[node][neighbor]
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return distances
```