数据结构与算法 / 系统课时
优先队列版 Dijkstra 怎么写
优先队列版 Dijkstra 怎么写
在稀疏图上直接扫描所有未确定顶点会浪费大量时间,常用写法是用最小堆保存当前候选距离。Python 的 heapq 没有 decrease-key 操作,因此实现重点是允许同一顶点重复入堆,并在弹出时跳过已经过期的状态。
学习目标
- 用邻接表和最小堆实现可运行的 Dijkstra
- 正确处理重复入堆与过期状态
- 说明该实现的复杂度与适用边界
堆里保存什么
维护 dist[u] 表示当前已知从源点到 u 的最短距离,优先队列保存二元组 (distance, vertex)。当松弛得到更短距离时,不修改堆中旧记录,而是直接压入一条新记录。
于是同一顶点可能同时存在多个候选值。弹出 (d, u) 后,若 d != dist[u],说明更短的记录已经在之后写入 dist[u],当前记录已经过期,直接跳过即可。
这种“惰性删除”写法非常适合 heapq:代码简单,不需要维护顶点在堆中的位置,也不会破坏最短路结果。
完整实现与验证
下面使用 0 到 n - 1 的整数作为顶点编号,邻接表中的每条边表示 (终点, 权重)。函数会先拒绝负权边,因为 Dijkstra 的正确性依赖非负边权。
from heapq import heappop, heappush
from math import inf
def dijkstra(graph, source):
n = len(graph)
# 先检查算法前提,避免把负权图误交给 Dijkstra。
for edges in graph:
for _, weight in edges:
if weight < 0:
raise ValueError('Dijkstra requires non-negative edge weights')
dist = [inf] * n
prev = [-1] * n
dist[source] = 0
pq = [(0, source)]
while pq:
d, u = heappop(pq)
# 同一顶点可能多次入堆,只展开当前最新的最短记录。
if d != dist[u]:
continue
for v, weight in graph[u]:
nd = d + weight
if nd < dist[v]:
dist[v] = nd
prev[v] = u
heappush(pq, (nd, v))
return dist, prev
def restore_path(prev, dist, target):
if dist[target] == inf:
return []
path = []
while target != -1:
path.append(target)
target = prev[target]
return path[::-1]
if __name__ == '__main__':
graph = [
[(1, 4), (2, 1)],
[(3, 1)],
[(1, 2), (3, 5)],
[],
]
dist, prev = dijkstra(graph, 0)
for target in range(len(graph)):
path = restore_path(prev, dist, target)
print(f'{target}: dist={dist[target]}, path={path}')预期输出
0: dist=0, path=[0]
1: dist=3, path=[0, 2, 1]
2: dist=1, path=[0, 2]
3: dist=4, path=[0, 2, 1, 3]顶点 1 会先以距离 4 入堆,随后经顶点 2 被更新为距离 3,于是堆中同时存在 (4, 1) 和 (3, 1)。距离 3 的记录先弹出并展开;以后弹出距离 4 的旧记录时,d != dist[1] 成立,因此不会重复扫描顶点 1 的出边。
重复入堆为什么不会出错
每次只有在 nd < dist[v] 时才更新距离并压入新状态,所以 dist[v] 始终保存目前发现的最好值。旧状态仍留在堆中,但它携带的距离大于当前 dist[v],被弹出时会被过滤。
这个判断主要用于避免重复工作。即使某些写法不跳过旧状态,只要仍以正确条件松弛,通常也不会把更差距离写回 dist,但会反复遍历邻边,显著增加运行时间。生产代码应保留过期状态检查。
复杂度与边界
在这种惰性删除实现中,每次成功松弛都可能产生一次入堆,因此堆中记录数最坏可到 O(E),时间复杂度可写为 O((V + E) log E);对普通简单图,通常也写成常见的 O((V + E) log V)。除邻接表外,距离、前驱数组需要 O(V) 空间,堆最坏需要 O(E) 额外空间。
这份实现适合非负权的单源最短路,尤其是稀疏图。若存在负权边,应改用 Bellman-Ford 或利用 DAG 等特殊结构;若只需要无权图最短路,则 BFS 更简单,也能在线性时间完成。