3.4 Dijkstra 算法

贪心卷的收官之作，是图算法里最负盛名的 Dijkstra 算法——单源最短路径。它求从一个起点到其他所有顶点的最短距离，是导航、网络路由、地图服务的基础。它还引入图算法最核心的操作——松弛（relaxation），这个操作在第五卷会反复出现。

1.问题：从一个点到所有点的最短路

给一个边权非负的有向（或无向）图 $G=(V,E)$ ，给一个源点 $s$ ，求 $s$ 到每个其他顶点的最短距离。

"非负"是关键前提——Dijkstra 不能处理负权边（下一段说为什么）。如果允许负权，得用第五卷 5.2 的 Bellman-Ford。

2.核心思想：贪心地确认最短，靠松弛传播

Dijkstra 维护一个想法：已确认最短距离的顶点集合 $S$ （一开始只有源点 $s$ ，距离 0）。每一轮，从"还没确认"的顶点里，挑当前估计距离最小的，确认它（加入 $S$ ），然后用它去松弛它的邻居。

松弛（relaxation）是图算法的灵魂操作，值得单独讲清：

RELAX(u, v, w)         // u 已确认，v 是 u 的邻居
    if dist[u] + w(u,v) < dist[v]:   // 经过 u 到 v 更近？
        dist[v] = dist[u] + w(u,v)    // 就更新 v 的估计
        parent[v] = u

一句话："如果经过 u 走到 v 比已知的更近，就更新 v"。 整个 Dijkstra 就是在反复松弛，让距离估计一步步逼近真值。

DIJKSTRA(G, s)
    初始化：dist[s]=0，其余 dist=∞
    S = ∅（已确认集）
    Q = 所有顶点的最小堆（按 dist）
    while Q 非空:
        u = EXTRACT-MIN      // 当前估计最小的未确认顶点
        S = S ∪ {u}          // 确认它（它的距离就是最短的）
        for 每条出边 (u,v):
            RELAX(u, v, w)   // 松弛邻居；若 dist 更新，更新堆

3.为什么"确认了就不回头"是对的

Dijkstra 的贪心赌注是：一旦某顶点被 EXTRACT-MIN 取出（当前估计最小），它的距离就一定是最终最短，再也不会被更新。 这个赌注在非负权下成立，证明直觉如下：

设 $u$ 被取出时距离为 $d[u]$ 。假设 $d[u]$ 不是最短——那存在某条更短的路径到 $u$ ，这条路径必经过某个还没确认的顶点 $x$ 。但因为边权非负，经过 $x$ 再到 $u$ 的距离 $\ge d[x]$ ，而 $d[x]\ge d[u]$ （ $u$ 是当前最小）——矛盾。所以 $d[u]$ 就是最短。

负权边会破坏这个证明：如果某条边是负的，"经过 $x$ 再到 $u$ "可能反而更短， $d[x]\ge d[u]$ 不再保证 $\text{路径}\ge d[u]$ ，贪心确认就错了。这就是 Dijkstra 不能处理负权的根本原因。

4.复杂度：堆让它变成 $O((V+E)\log V)$

朴素实现（每次线性找最小）： $O(V^2)$ ，适合稠密图。

用最小堆（优先队列）：每次 EXTRACT-MIN 是 $O(\log V)$ ，共 $V$ 次；每条边可能触发一次松弛（更新堆 $O(\log V)$ ），共 $E$ 次。总计 $O((V+E)\log V)$ 。堆让 Dijkstra 在稀疏图上高效——又是 1.4 优先队列的用武之地。

5.松弛：图算法的通用原子操作

值得强调：松弛不只属于 Dijkstra。它是几乎所有最短路、最小费用流算法的通用原子操作。第五卷你会看到：

Bellman-Ford（5.2）：对所有边反复松弛 $|V|-1$ 轮，能处理负权。
SPFA：Bellman-Ford 的队列优化。
最小费用流（5.6）：在残量图上反复松弛找最短增广路。

"松弛"这个操作的普适性，是图算法最深刻的设计模式之一——第十一卷 11.5 会把它提炼成"松弛法"。现在你先体会：很多看似不同的图算法，底层都是"反复松弛直到收敛"。

6.练习

Q1. Dijkstra 为什么要求边权非负？给一个负权边让它出错的例子。

Dijkstra 赌"取出即最短"，靠的是"经过未确认点 $x$ 的路径 $\ge d[x]\ge d[u]$ "，这只在边权非负时成立。若有负权边，比如 A→B 权 5、A→C 权 2、C→B 权 -10。Dijkstra 先确认 C（dist 2），再确认 B（dist 2+5=7 经... 实际会先确认 dist 较小的，但确认 B 时认为最短是某值，殊不知经 C→B 的 -10 能让 B 的距离变成 2-10=-8，更短）。负权让"已确认"不再保证最优。

Q2. 松弛操作 RELAX(u,v) 在做什么？为什么它是图算法的通用原子？

松弛是"若经 u 到 v 比已知更近，就更新 v 的估计"。它是几乎所有最短路/最小费用流算法的原子：Dijkstra 反复松弛已确认点的邻居，Bellman-Ford 反复松弛所有边，最小费用流在残量图上松弛找增广路。不同算法的差别，本质是"松弛的顺序和策略"不同——这是图算法最深刻的设计模式（第十一卷"松弛法"）。

Q3.（思考题） 用最小堆的 Dijkstra 复杂度 $O((V+E)\log V)$ ，朴素线性找最小是 $O(V^2)$ 。各适合什么图？

朴素 $O(V^2)$ 适合稠密图（ $E\approx V^2$ ，此时 $(V+E)\log V\approx V^2\log V$ 反而比 $V^2$ 大，朴素更优）。堆优化 $O((V+E)\log V)$ 适合稀疏图（ $E\approx V$ ，变成 $O(V\log V)$ ，远好于 $V^2$ ）。选哪个，取决于图的稠密度——这是 1.8 节" $n$ 是谁、规模关系如何"的实战。

7.小结

Dijkstra 用"贪心确认 + 松弛传播"， $O((V+E)\log V)$ 求出非负权图的单源最短路。它的命门是"非负权"（保证取出即最短），灵魂是松弛操作。松弛是图算法的通用原子，第五卷会反复用到。贪心卷到此结束——下一篇我们跨过分水岭，进入动态规划的世界。