一文读懂dijkstra算法
时间: 2024-12-31 08:37:07 浏览: 33
Dijkstra算法概述
Dijkstra算法是一种用于解决单源最短路径问题的经典贪心算法[^1]。该算法能够找到加权图中从起始顶点到其他所有顶点的最短路径。
算法特点
- 只适用于边权重非负的情况。
- 对于稀疏图效率较高,适合处理大规模数据集。
- 时间复杂度为O((V+E)log V),其中V表示顶点数量,E代表边的数量。
工作机制描述
初始化阶段设置起点的距离为0,其余各点设为无穷大。随后按照如下方式迭代更新:
- 从未访问过的节点集合里选取当前距离最小的一个作为考察对象;
- 遍历此节点相邻接的所有未被标记过的邻居结点;
- 如果经过当前节点到达某邻近节点的新路径长度小于已记录值,则替换旧值并保存前驱信息;
当全部节点均已完成探索或目标终点已被触及之时终止循环操作流程。
import heapq
def dijkstra(graph, start):
queue = []
distances = {node: float('infinity') for node in graph}
predecessors = {node: None for node in graph}
distances[start] = 0
heapq.heappush(queue, (0, start))
while queue:
current_distance, current_node = heapq.heappop(queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
predecessors[neighbor] = current_node
heapq.heappush(queue, (distance, neighbor))
return distances, predecessors
相关推荐
![-](https://img-home.csdnimg.cn/images/20241231044955.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231045021.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)