只关心"从一个点出发"的最短路，不需要 Floyd 那种任意两点都算一遍的高昂代价——贪心地每次确定当前最近的点，像水波一样一圈圈地把距离确定下来。
15.2 节的 Floyd 能算出任意两点之间的最短距离，但代价是 O(n³)，点数一多就跑不动了。如果只关心"从某一个固定的起点出发，到图中所有点的最短距离"（单源最短路），完全没必要把"任意两点"都算一遍——Dijkstra 算法正是针对这个更常见的场景设计的，用贪心的思路把复杂度降到 O((V+E) log V)，能应付大得多的图。
14.4 节的 A* 其实已经用到了 Dijkstra 的核心机制，只是多加了一个启发函数 h(n)；如果把 A* 的 h(n) 恒定设为 0，就直接退化成了本节的 Dijkstra——这一点在 14.4 节 ⑥ 已经提过。
Dijkstra 的过程可以概括成一句话：每次从"还没确定最短距离"的点里，挑出当前已知距离最小的那个，把它的距离"钉死"为最终答案，再用它去尝试缩短它邻居的距离。这是一个贪心策略——之所以"距离最小的点，它的距离就已经是最终答案"，是因为如果还存在更短的路径，那条路径必然要经过某个"距离更大"的中间点，而这与"当前它是距离最小的点"矛盾。
用优先队列（小顶堆）维护"当前已知距离"，每次弹出距离最小的点，正好实现这个贪心顺序。
| 步骤 | 做什么 |
|---|---|
| 初始化 | 起点距离设为 0，其余所有点距离设为 INF；把 (0, 起点) 放入优先队列 |
| 取出 | 每次从优先队列弹出"距离最小"的点 u |
| 松弛 | 枚举 u 的所有邻居 v，如果"经过 u 到 v"比 v 当前记录的距离更短，就更新 v 的距离，并把新距离连同 v 一起push进队列 |
| 结束 | 优先队列为空时，所有能到达的点都已经算出最短距离 |
还是 15.1、15.2 节的示例图（A-B=4，A-C=1，B-C=2，B-D=5，C-D=8），从 A 出发跑一遍 Dijkstra，全程追踪优先队列的弹出顺序：
| 弹出 | 松弛了谁 | dist[A] | dist[B] | dist[C] | dist[D] |
|---|---|---|---|---|---|
| (0, A) | B：0+4=4；C：0+1=1 | 0 | 4 | 1 | ∞ |
| (1, C) | B：1+2=3<4；D：1+8=9<∞ | 0 | 3 | 1 | 9 |
| (3, B) | D：3+5=8<9 | 0 | 3 | 1 | 8 |
| (4, B) | 过时记录，dist[B] 已经是 3，4>3，直接跳过 | ||||
| (8, D) | 无更优更新 | 0 | 3 | 1 | 8 |
| (9, D) | 过时记录，dist[D] 已经是 8，9>8，直接跳过 | ||||
dist[A]=0, dist[B]=3, dist[C]=1, dist[D]=8——和 15.2 节 Floyd 算出的结果完全一致（Floyd 那一节最终矩阵的第一行正是 0, 3, 1, 8），说明两种算法确实是在求解同一个问题，只是思路和适用场景不同。表格里两行"过时记录"是因为 B、D 都被更新过不止一次：(4,B) 是第一次从 A 松弛时push进队列的，后来被经过 C 中转的更短路径 (3,B) 取代，但旧的 (4,B) 依然留在队列里，弹出时需要识别并跳过。| 1 | const int INF = 0x3f3f3f3f; |
| 2 | vector<pair<int,int>> adj[MAXN]; // adj[u]：(邻居, 边权)，见 15.1 节邻接表 |
| 3 | int dist_[MAXN]; |
| 4 | |
| 5 | void Dijkstra(int s, int n) |
| 6 | { |
| 7 | fill(dist_ + 1, dist_ + 1 + n, INF); |
| 8 | dist_[s] = 0; |
| 9 | priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; // ★ greater<>：小顶堆，默认是大顶堆 |
| 10 | pq.push({0, s}); |
| 11 | |
| 12 | while (!pq.empty()) |
| 13 | { |
| 14 | auto [d, u] = pq.top(); pq.pop(); // ★ 每次弹出当前距离最小的点 |
| 15 | if (d > dist_[u]) continue; // 过时的队列项，跳过（和 14.4 节 A* 同样的技巧） |
| 16 | for (auto [v, w] : adj[u]) |
| 17 | { |
| 18 | if (dist_[u] + w < dist_[v]) // 松弛：经过 u 到 v 是否比目前记录的更短 |
| 19 | { |
| 20 | dist_[v] = dist_[u] + w; |
| 21 | pq.push({dist_[v], v}); |
| 22 | } |
| 23 | } |
| 24 | } |
| 25 | } |
H(v)"这一步去掉——第 21 行 push 进队列的就是纯粹的 dist_[v]，没有加任何启发式估计。第 15 行"跳过过时记录"的技巧也是两者共用的，这正呼应了 ① 提到的"Dijkstra 是 A* 在 h=0 时的特例"。每条边最多会导致一次 push（松弛成功时），所以队列里总共最多有 O(E) 个元素；每次 pop、push 操作在优先队列上的代价是 O(log E)（约等于 O(log V)）。总时间复杂度是 O((V+E) log V)——比 Floyd 的 O(V³) 在稀疏图上快得多，能应对点数上万甚至更多的图。
| 对比项 | Floyd（15.2 节） | Dijkstra（本节） |
|---|---|---|
| 解决的问题 | 任意两点之间的最短距离 | 从一个固定起点到所有点的最短距离 |
| 时间复杂度 | O(V³) | O((V+E) log V) |
| 能否处理负权边 | 可以（只要没有负权环） | 不能（见 ⑥ 陷阱） |
| 适合场景 | 点数较少，需要全源最短路 | 点数较多，只需要单源最短路 |
greater<>，优先队列默认是大顶堆：C++ 的 priority_queue 不加额外模板参数时，默认每次弹出最大的元素——Dijkstra 需要每次拿到距离最小的点，必须显式传入 greater<> 改成小顶堆，或者把距离取相反数塞进默认的大顶堆（两种写法效果一样，前者更直观）。