数据结构与算法 / 系统课时

优先队列版 Dijkstra 怎么写

优先队列版 Dijkstra 怎么写

在稀疏图上直接扫描所有未确定顶点会浪费大量时间,常用写法是用最小堆保存当前候选距离。Python 的 heapq 没有 decrease-key 操作,因此实现重点是允许同一顶点重复入堆,并在弹出时跳过已经过期的状态。

学习目标

  • 用邻接表和最小堆实现可运行的 Dijkstra
  • 正确处理重复入堆与过期状态
  • 说明该实现的复杂度与适用边界

堆里保存什么

维护 dist[u] 表示当前已知从源点到 u 的最短距离,优先队列保存二元组 (distance, vertex)。当松弛得到更短距离时,不修改堆中旧记录,而是直接压入一条新记录。

于是同一顶点可能同时存在多个候选值。弹出 (d, u) 后,若 d != dist[u],说明更短的记录已经在之后写入 dist[u],当前记录已经过期,直接跳过即可。

这种“惰性删除”写法非常适合 heapq:代码简单,不需要维护顶点在堆中的位置,也不会破坏最短路结果。

完整实现与验证

下面使用 0 到 n - 1 的整数作为顶点编号,邻接表中的每条边表示 (终点, 权重)。函数会先拒绝负权边,因为 Dijkstra 的正确性依赖非负边权。

python
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}')

预期输出

text
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 更简单,也能在线性时间完成。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

优先队列版 Dijkstra 怎么写

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通