Dijkstra算法不同优先队列性能对比

可视化演示

展示Dijkstra最短路径搜索过程，对比二叉堆/斐波那契堆/Radix Heap三种优先队列的堆结构与时间复杂度性能曲线。

算法基础：从快递员的日记本说起

小D翻开小本本，上面记着：1号小区目前 2 公里，2号小区 5 公里，3号小区“未知”。他永远只做一件事——找到“已记录距离”里最小的那个小区，立刻出发。这一选，就是 Dijkstra 的“贪心选择”（greedy choice）：眼前最近的，就是全局最近的，因为所有道路距离都是非负的，绕路不可能让已经最近的点变得更近。

在图论术语里，小区叫节点（vertex），道路叫边（edge），路上的数字叫边权（weight）。小D的日记本叫距离数组，而“绕到邻居家看看有没有更近的捷径”这个动作，教科书上叫松弛（relaxation）。松弛只有两种结果：新路线更短，则更新记录；否则原样保留。整个过程保证一件事：被标记为“已确定”的节点，它的距离值永远不再变化——因为所有可能更短的路都被排除过了。

小D的整个配送流程，就是“挑当前最近 → 锁定 → 顺路看邻居 → 更新日记本”四步循环。但他很快发现：从日记本里找“最小”如果一页页翻，一上午就废了。他需要一套能自动排序的“清单系统”——于是，优先队列闪亮登场。

优先队列原理：会自我排序的神秘清单

小D雇了秘书小Q专门管清单。小Q有一项绝活：清单永远保证“最重要”的卡片——也就是距离最短的那张——放在最顶上。小D任何时候伸手就能拿到，从不用翻找。这个“永远把最小放最顶”的抽象数据结构，就叫优先队列（Priority Queue）。

在 Dijkstra 里，优先队列至少干三件事：插入（insert，放一张新卡片进清单）、取出最小（extract-min，拿走最顶上那张）、降低键值（decrease-key，发现更短距离时改写卡片数字，并让它自动飞到合适位置）。不同的“整理策略”就是不同的堆，策略优劣用“操作步数”衡量——计算机科学家用大 O 记号描述它。Dijkstra 的总耗时，就是 n 次取出加上 m 次改写的总和。

同样的待办清单，有人用整齐卡片盒整理（二叉堆），有人攒一大堆等收盘才整理（斐波那契堆），有人按公里数把卡片塞进一格格的货架（Radix Heap）。接下来，我们挨个参观这三位秘书的办公方式。

二叉堆实现：一丝不苟的卡片盒

秘书小B的桌上有个透明卡片盒，卡片永远摆成“完全二叉树”形状：最上层一张，第二层两张……每张卡片只记着爸爸的位置。新卡片来时，小B先把它放到最后一排，然后让卡片“上浮”：和爸爸比大小，若比爸爸小就往上换，一路换到不再比爸爸小为止。取走最小卡片后，他把最后一张卡片移到根部，再让它“下沉”：跟两个儿子里较小的比，若比儿子大就换下去。

这套“上浮/下沉”的代价，每次最多等于树的高度。n 张卡片堆起来的完全二叉树，高度是 log₂n，所以插入和取出都是 O(log n)。在 Dijkstra 里，n 次取出约 O(n log n)，m 次入堆/更新约 O(m log n)，总复杂度：

卡片盒井井有条，但小B的缺点是每张卡片移动都得规规矩矩地交换位置。有没有更偷懒的办法？有——下一位秘书小F，干脆不整理了。

斐波那契堆：懒到极致的账本大师

秘书小F从不整理桌面。新订单来了，直接“啪”地把卡片甩在桌上，当成一棵孤零零的小树根——插入几乎零成本。发现某张卡片距离要改小？他直接拿笔把数字划掉，再把这张卡片连同它整棵小树“剪”下来，甩回桌面——这就是“懒策略”的精髓：平时不动，攒着。

这个“桌面”上一堆大小不一的树，就是斐波那契堆（Fibonacci Heap）。它只承诺一件事：取最小的时候认真打扫一次——把同级的树两两合并，挑最小的当根。因为有了摊还分析（amortized analysis）做保证，算总账时，每隔一段时间才来一次的大扫除成本，被平摊到每一次日常操作头上。于是“摊还”之后：插入和降低键值都是 O(1)，只有取出最小是 O(log n)。Dijkstra 总复杂度：

不过，小F的桌面乱得像垃圾堆。虽然“总工作量”的理论数字漂亮，但每棵树维护起来的常数开销很大，现实中多数工程反而被小B的卡片盒吊打。千万别被渐近复杂度骗了——实战的账要另算。

Radix Heap 基数堆：按公里数分格的货架

第三位秘书小R更是奇才。他先问小D：你的距离是不是整数公里？得到肯定答复后，他订制了一排货架：第 0 格放“0 公里”的卡片，第 1 格放“1 公里”，第 2 格放“2~3 公里”，第 3 格放“4~7 公里”……每格覆盖的区间翻倍扩大。这就是Radix Heap（基数堆），它利用“整数距离”这个特性，把卡片按距离区间塞进不同的桶。

因为同一格里的卡片距离都在同一区间，取最小时，小R只需从左往右扫，找到第一个非空格子——里面任意一张卡片就是当前最小（同区间内部不关心顺序，反正都会被取到）。货架整理时要做“批量迁移”：把卡片从宽区间格子挪到更精确的窄区间格子。货架格子数约 O(log C)，C 是最大边权；每张卡片被往左迁移的次数不超过 O(log C) 次。于是 Dijkstra 用 Radix Heap 的总代价：

小R这套玩法的唯一门槛：距离必须是非负整数，而且得预先知道大致范围。一旦满足，他送快递的速度快得像闪电；若边权是浮点数或负数，货架就会当场失灵。

性能与选型：到底该雇谁？

三位秘书各有绝活：小B规矩可靠，小F理论漂亮，小R条件苛刻。快递站站长拍板：看订单结构选人。若城市路网是“稀疏图”——n 个路口大约只有 n 条路，m 与 n 同阶，此时二叉堆 O(m log n) ≈ O(n log n) 已经极快，斐波那契堆的常数反而拖后腿；若图是“稠密图”——每个节点几乎直连所有其他节点，m 接近 n²，斐波那契堆的 O(m + n log n) 才真正显出含金量。

如果边权是“公里数”这类非负整数且范围有限，Radix Heap 的 O(m + n log C) 几乎线性，在路由表计算、算法竞赛中是常见杀手锏。还要牢记：Dijkstra 本身要求边权非负；一旦出现负权边，贪心前提崩塌，得换贝尔曼-福特算法。选型判据可以浓缩成：

最终快递站的配置单是：日常配送（稀疏道路网）用二叉堆；科研验证理论极限用斐波那契堆；系统里全是整数开销（比如路由器跳数）就上 Radix Heap。记住，在真实工程里，“够快、简单、Bug 少”往往比“渐近复杂度最优”更重要。

AI 应用场景

Python 演示

import heapqimport randomimport time  def dijkstra_binary_heap(n, edges, src=0):    # 二叉堆版 Dijkstra    g = [[] for _ in range(n)]    for u, v, w in edges:        g[u].append((v, w))        g[v].append((u, w))    dist = [float('inf')] * n    dist[src] = 0    pq = [(0, src)]    while pq:        d, u = heapq.heappop(pq)        if d > dist[u]:            continue        for v, w in g[u]:            nd = d + w            if nd < dist[v]:                dist[v] = nd                heapq.heappush(pq, (nd, v))    return dist  def dijkstra_radix_heap(n, edges, src=0, max_w=100):    # 整数桶式优先队列版 Dijkstra (Dial Algorithm 思想)    g = [[] for _ in range(n)]    for u, v, w in edges:        g[u].append((v, w))        g[v].append((u, w))    dist = [float('inf')] * n    dist[src] = 0    buckets = {0: [src]}    while buckets:        cur_d = min(buckets)        node = buckets[cur_d].pop()        if not buckets[cur_d]:            del buckets[cur_d]        if cur_d > dist[node]:            continue        for v, w in g[node]:            nd = cur_d + w            if nd < dist[v]:                dist[v] = nd                buckets.setdefault(nd, []).append(v)    return dist  def random_graph(n, m, max_w=100):    # 生成无重边的随机无向图    edges = set()    while len(edges) < m:        u = random.randrange(n)        v = random.randrange(n)        if u != v and (min(u, v), max(u, v)) not in edges:            a, b = min(u, v), max(u, v)            edges.add((a, b))            yield a, b, random.randrange(1, max_w + 1)  if __name__ == '__main__':    n, m = 3000, 12000    edges = list(random_graph(n, m))    t0 = time.perf_counter()    d1 = dijkstra_binary_heap(n, edges)    t1 = time.perf_counter()    d2 = dijkstra_radix_heap(n, edges)    t2 = time.perf_counter()    print('二叉堆版本耗时 %.4f 秒' % (t1 - t0))    print('桶式版本耗时 %.4f 秒' % (t2 - t1))    print('两种算法结果一致:', d1 == d2)

1. pq = [(0, src)]把源点放进堆，距离 0 的元组位于堆顶。
2. d, u = heapq.heappop(pq)取出当前距离最小的节点，对应 extract-min。
3. if d > dist[u]: continue惰性删除：堆里过时的旧记录直接跳过。
4. if nd < dist[v]: dist[v] = nd松弛：发现更短路线就立即更新距离表。
5. heapq.heappush(pq, (nd, v))新距离入堆，等价于一次堆插入。
6. buckets = {0: [src]}桶式队列初始化：距离 0 的节点塞进 0 号桶。
7. cur_d = min(buckets)找最小非空桶，模拟 Radix 的“从左往右找第一格”。
8. del buckets[cur_d]桶取空就删除，保证字典永远只含待处理的桶。
9. buckets.setdefault(nd, []).append(v)新最短距离放进对应桶，平均 O(1)。
10. while len(edges) < m:循环生成直到凑够 m 条无重边，保证测试公平。

常见误区

面试题