Dijkstra算法python
时间: 2024-12-31 20:46:12 浏览: 5
### 关于Dijkstra算法的Python实现
#### Dijkstra算法简介
Dijkstra算法是一种经典的单源最短路径算法,用于在加权图中找出从一个指定起点节点到其他所有节点的最短路径。该算法适用于含有非负权重边的有向和无向图[^1]。
#### Python代码示例及解释
下面是一个基于优先队列优化版本的Dijkstra算法Python实现:
```python
import heapq
def dijkstra(graph, start):
# 初始化距离字典,默认值为无穷大
distances = {node: float('infinity') for node in graph}
# 起始节点的距离设为0
distances[start] = 0
# 创建最小堆,存储 (distance, node) 对
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_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
# 将新发现的较短路径加入优先队列
heapq.heappush(priority_queue, (distance, neighbor))
return distances
if __name__ == "__main__":
# 构建测试用图结构
test_graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
result = dijkstra(test_graph, 'A')
print(result)
```
这段程序实现了如下功能:
- 使用`heapq`模块来维护一个小顶堆作为优先级队列;
- `distances`字典用来保存各个结点到起始结点之间的最短路径长度;
- 当前处理过的结点会被标记并移入已访问列表(这里通过比较`current_distance`与已有记录决定是否继续),从而避免重复遍历;
- 每次从未被确认最短路经的集合U选取离原点最近的一个点u,并将其纳入S集合作进一步扩展操作直至完成整个过程[^3]。
阅读全文