Dijkstra 最短路径算法

2026-06-02

Dijkstra = BFS + 贪心。把 FIFO 队列换成优先队列，每次从未确定的节点里挑距离最小的那个去松弛邻居。前提:边权非负——因为已确定节点的距离一旦敲定就不再回头。

直觉 —— 为什么是 “BFS + 贪心”

BFS 在等权图里是对的:从起点一层一层扩,第一次摸到某节点就是最短路。原因是 FIFO 保证”先入队的距离小”。

边权不等怎么办?把队列升级成优先队列(小顶堆),依然每次取出”目前距离最小”的节点。这个节点的距离从此就敲定了——其他人想绕路过来,只会更远(因为边权 ≥ 0)。这就是贪心的来源。

口诀:“挑最近的未确定节点,扩它的邻居”。整个算法就这一句话。

负权为什么会破坏它

贪心的根基是”已确定的不再变”。一旦有负边,绕远路反而可能更短,刚敲定的距离就会被推翻。举个反例:

1
2
3

A→B: 1
A→C: 5
C→B: -10

从 A 出发,Dijkstra 先弹出 B,敲定 dist[B]=1,然后再也不看 B 了。但真实最短是 A→C→B = 5 + (-10) = -5。算法已经走过头,回不去。

边权全 1 → 普通 BFS。边权 0/1 → 0-1 BFS(双端队列)。有负权 → Bellman-Ford / SPFA。

动画 —— 跟着堆的弹出顺序走一遍

下面动画从节点 0 出发。重点看两件事:

每一步弹出的节点——一定是当前 dist 数组里(未确定节点中)的最小值。
松弛后哪些格子被刷黄——只有”新距离 < 旧距离”才更新,被更新的节点会重新进堆。

看完一遍后,把它和”BFS 一层一层扩”对比:Dijkstra 不是按层,而是按已知距离从小到大逐个敲定。

模板 —— Python with heapq

import heapq

def dijkstra(n, edges, src):
    g = [[] for _ in range(n)]
    for u, v, w in edges:
        g[u].append((v, 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

三个写法上的关键点:

堆里存 (距离, 节点)——元组比较从第一个元素开始,自动按距离排序。
if d > dist[u]: continue——堆里可能有同一节点的多份旧条目(Python 的 heapq 不支持 decrease-key,只能反复 push)。这行跳过过期的,正确性可以不要,但不加会做大量无用松弛。
先更新 dist[v] 再 push——不要”先 push 再判断”,会让堆爆炸。

复杂度。

变种 —— 同一框架的不同换皮

变种	改动	何时用
A*	堆的 key 改成 `g(n) + h(n)`,h 是到终点的启发式估计	单源单点,有几何/距离先验,如游戏寻路
双向 Dijkstra	从起点和终点各跑一遍,在中间相遇	单源单点,需要剪掉大量无关搜索
0-1 BFS	边权只有 0/1,把堆换成 deque,0 加队头、1 加队尾	边权 0/1,
分层图 / 状态扩维	节点变成 `(node, state)`,如剩余免费次数	状态影响转移代价
Bellman-Ford	不用堆,V 轮松弛所有边	有负权,
SPFA	队列版 Bellman-Ford,平均更快	有负权,稀疏图

记住骨架:“用什么数据结构维护待扩展节点”——FIFO 是 BFS,小顶堆是 Dijkstra,deque 是 0-1 BFS,全扫一遍是 Bellman-Ford。

经典题

热身:

743. 网络延迟时间 —— 模板
1631. 最小体力消耗路径 —— “路径权”改成 max 而非 sum
787. K 站中转内最便宜的航班 —— 状态扩维 (node, stops)

进阶:

1514. 概率最大的路径 —— 大顶堆 + log 转化(乘法变加法)
1928. 规定时间内到达终点的最小花费 —— (cost, time, node) 双维度
2045. 到达目的地的第二短时间 —— 维护前两小距离
1976. 到达目的地的方案数 —— Dijkstra 顺便数路径
407. 接雨水 II —— 堆 + 从边界向内”灌水”

记忆法 / 易错点

记忆法:一句话——“挑最近的未确定节点,扩它的邻居”。看到”非负边权 + 单源最短路”,立刻条件反射 heapq。

易错点:

过期条目没跳过:if d > dist[u]: continue 不写就 TLE。
负权:看到负边立刻换 Bellman-Ford,别硬上 Dijkstra。
路径权不是 sum:1631 这种 max-of-edges,松弛时用 max(d, w) 而非 d + w。模板要灵活。
状态需要扩维:出现”K 次免费”、”限制时间”等约束,节点必须变成元组。
大顶堆:Python 的 heapq 是小顶堆,要大顶堆就 push 负数。

思考题

为什么 Dijkstra 不能处理负权边?给一个反例。

贪心地”确定”当前最小距离节点,确定后不再更新。若后续负边能让已确定节点更短,无法回头。反例:A→B(1)、A→C(5)、C→B(-10),从 A 出发先确定 dist[B]=1,但实际最短 A→C→B = -5。

if d > dist[u]: continue 这一行不加会怎样?

堆里可能有同一节点的多份旧条目(因为 heapq 不支持 decrease-key)。不跳过过期条目,正确性不受影响,但会用旧距离去松弛邻居,做大量无用功,复杂度退化。

0-1 BFS 为什么比 Dijkstra 更快(边权只有 0/1 时)?

用双端队列:权 0 的边加到队头,权 1 的边加到队尾。每个节点最多入队两次,无 heap 比较的 log, vs Dijkstra 的。