Lesson 0411 · 最短路 I：Dijkstra

④ 数据结构与算法 — 第 11 课

1. 为什么 BFS 不管用了

三点：1→2 路费 5，1→3 路费 1，3→2 路费 1。

1 --5--> 2
1 --1--> 3 --1--> 2

到 2 号：直达 5，绕一趟 1+1 = 2   ← 绕路更便宜

BFS 只数边：它一步就能踩到 2 号，于是报「2 号 = 1 步」，然后就再也不回头看 2 号了 —— 可真正便宜的路要绕两跳。错的原因是 BFS 有个隐含前提：多走一条边一定不便宜。边权非负这个前提还在，但「每条边一样贵」没了。

所以要换一个衡量标准：不算「走了几步」，算「花了多少钱」。

2. 松弛：本课唯一的新动作

整个 Dijkstra 只有两个动作，第一个就是松弛（relax）。名字很唬人，做的事一句话：

if (dis[u] + w < dis[v]) dis[v] = dis[u] + w;      // 就这一行

dis[x] 的含义始终是：「目前已知的」从起点到 x 的最短距离。注意「目前已知」四个字 —— 它一开始是 INF（∞，代表「还不知道怎么去」），靠松弛一次次变小。松弛不会让答案变差，只会让它更接近真相。

手推一遍：四个点

图（有向、带权）：

1 --7--> 2 --1--> 4
1 --2--> 3 --100--> 4
         3 --3--> 2

起点 1。每一轮做两件事：① 挑未定点里 dis 最小的 → 盖章；② 拿它去松弛它的出边。

答案：1=0、2=5、3=2、4=6。

请注意第 2 轮：3→4 那条边权 100，先把 4 写成 102；第 3 轮发现「绕 2 号过去只要 6」，又把它改小了。这就是松弛的意义 —— 允许先给一个粗糙的答案，再慢慢改好。

3. 为什么敢「盖章」

把「盖章」写成代码是一次 done[u] = true，之后再也不会修改 u 的距离。这个操作听起来很危险 —— 万一以后出现更便宜的路呢？

用一句话回答：以后出现的任何路，都要先经过一个还没盖章的点；而那些点的距离都不小于 u，边权又非负，所以绕过去只会更贵。

把它写成反证，只有三行：

1. 假设 u 被盖章时 dis[u] 不是最终答案，真实最短距离 D < dis[u]。
2. 真实路径上必然有一个还没盖章的点 x（起点没盖章时就是它），而且路是「起点 … x … u」，所以 dis[x] ≤ 到 x 的距离 ≤ D < dis[u]。
3. 可「dis 最小」的未定点是 u，任何未定点 x 都该有 dis[x] ≥ dis[u] —— 矛盾。所以 D 不可能小于 dis[u]。

这个证明里唯一用到「边权非负」的地方是第 2 步的「到 x 的距离 ≤ D」：因为从 x 往后走到 u 的路费加起来 ≥ 0，所以到 x 一定不比起点的总距离 D 更贵。边权一旦可以是负数，这句话就崩了 —— 这正是 0412 要讲的内容（届时你会看到 Dijkstra 在负权图上悄悄给出错误答案）。

三个常见的困惑

4. 朴素版：先写对，再写快

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int n, m, s;
vector<vector<pair<int,int>>> g;      // g[u] = {v, w}，g[u][i].first = 边终点

void dijkstra_naive() {
    vector<int> dis(n + 1, INF);
    vector<bool> done(n + 1, false);          // 是否已盖章
    dis[s] = 0;

    for (int round = 1; round <= n; round++) {
        // ① 挑：未定点里 dis 最小的
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (!done[i] && dis[i] != INF && (u == -1 || dis[i] < dis[u])) u = i;
        if (u == -1) break;                  // 剩下的点都到不了，提前结束
        done[u] = true;                      // ② 盖章

        // ③ 松弛它的所有出边
        for (auto [v, w] : g[u])
            if (dis[u] + w < dis[v]) dis[v] = dis[u] + w;
    }

    for (int i = 1; i <= n; i++)
        cout << (dis[i] == INF ? -1 : dis[i]) << (i == n ? '\n' : ' ');
}

拿 P4779 的样例逐轮跑一遍

这就是上面这份程序实际打印出来的过程（样例：4 6 1，边 1→2 (2)、2→3 (2)、2→4 (1)、1→3 (5)、3→4 (3)、1→4 (4)）：

输出 0 2 4 3 —— 和样例答案一致。
顺带一个细节：第 3 轮挑的是 4 号（dis=3），比 3 号（dis=4）先盖章。这并不是「按编号顺序」，而是「按 dis 从小到大」。后面用堆优化，靠的就是这个顺序。

5. 朴素版慢在哪：一次实测

朴素版每一轮都要「扫描一遍所有点找最小」，n 轮就是 O(n²)。实测（随机图、边权 1–1000、本机 g++ 16.2.0 -O2，只计算法本身、不含读入）：

看清楚最后一行：n 只从 1 万涨到 10 万，朴素版从 0.2 秒涨到 30 秒（平方增长），而 P4779 的时限是 1000 ms。朴素版在 P4779 上必超时，必须换数据结构。

6. 堆优化：把「找最小」交给堆

瓶颈在于每轮都要扫一遍点找最小。找最小值这件事，堆天生就拿手：

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int n, m, s;
vector<vector<pair<int,int>>> g;
long long ans = 0;          // 按题目要求加和（P4779 要这个）

void dijkstra_heap() {
    vector<int> dis(n + 1, INF);
    // 小根堆：存 {距离, 点}。priority_queue 默认是大根堆，用 greater 反过来
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    dis[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du > dis[u]) continue;            // 过期记录，跳过（懒删除）
        // 这里 u 就是当前未定点里 dis 最小的，直接盖章
        for (auto [v, w] : g[u]) {
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});         // 变小的点入堆
            }
        }
    }
    // 输出 n 个数（P4779 的数据保证 s 能到所有点）
    for (int i = 1; i <= n; i++) cout << dis[i] << (i == n ? '\n' : ' ');
}

效果：同一张 n = 105、m = 2×105 的图，朴素版 30.2 秒，堆优化 9.1 ms —— 差约 3300 倍。
复杂度从 O(n²) 变成 O(m log m)（每条边最多产生一次入堆，每次进出堆 log）。

7. 懒删除：if (du > dis[u]) continue;

一个点可能被松弛变小好几次，每变一次就入堆一次，于是堆里躺着同一号的好几个旧距离。比如 2 号先以 7 入堆，后来变成 5 又入堆一次 —— 等 5 那条出堆时，7 那条还躺在里面。

有两种处理办法：

1. 勤快删除：真的去堆里把旧的那条删掉。麻烦（堆不提供按值删除）。
2. 懒删除：不管它，等它出堆时检查一下 —— 如果堆里的值比现在的 dis[u] 大，说明它是过期货，continue 跳过。

auto [du, u] = pq.top(); pq.pop();
if (du > dis[u]) continue;      // 过期的旧记录，丢掉

8. 语法拆解（这一段专门给「看不懂那些尖括号」的人）

9. 完整模板（P4779 可直接用）

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int n, m, s;
vector<vector<pair<int,int>>> g;

int main() {
    ios::sync_with_stdio(false);     // 关掉 C 与 C++ 的流同步
    cin.tie(nullptr);                // 切断 cin 与 cout 的绑定
    cin >> n >> m >> s;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    vector<int> dis(n + 1, INF);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    dis[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du > dis[u]) continue;
        for (auto [v, w] : g[u])
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
            }
    }
    for (int i = 1; i <= n; i++) cout << dis[i] << (i == n ? '\n' : ' ');
    return 0;
}

读 2×10⁵ 行数据要多快？实测

P4779 的输入有 m ≤ 2×105 行「u v w」。同一份文件，三种读法各跑三遍取最快（本机 g++ 16.2.0 -O2，三者的读入结果完全一致）：

P4779 的时限是 1000 ms。用 cin 却不关同步，等于白扔 300 多毫秒（三分之一的时间）；关掉之后这 300 毫秒全拿回来。

10. 坑点清单

• 「最小」的定义必须是 <：写成 if (dis[u] + w <= dis[v]) 会在边权为 0 的图上反复入堆，慢到超时。
• 盖章标记：朴素版要 done[]；堆优化版靠 if (du > dis[u]) continue; 就够，两个都写也不会错（多一层保险）。
• 不可达的点：输出前要判断 dis[i] == INF，否则会打印 1061109567 这种数字（P3371 要求输出 2³¹-1）。
• dis 要设成 INF，不是 0；只有 dis[s] = 0。
• 有重边不用管：直接 push_back，两条边都存，跑的时候取小的那条。
• 边权相乘或相加可能溢出：距离是路径上所有边权之和，题目给的范围要自己算一遍上限，必要时换 long long。
• Dijkstra 只能处理非负权：出现负权边必须换算法（0412 的 Bellman-Ford / SPFA）。
• 加层数或边数限制的最短路不能直接套：那种题的正确性论证不成立，得用分层图或 DP。

11. 小测

12. 动手练习

1. P4779 【模板】单源最短路径（标准版） —— 用上面的模板就能过，n ≤ 105、m ≤ 2×105。注意要加那两行快读。
2. P3371 【模板】单源最短路径（弱化版） —— 和 P4779 的区别在输出：到不了的点要输出 2³¹-1，而且可能有重边。判 dis[i] == INF 时别用错的常数。
3. 选做：P1629 邮递员送信 —— 要算「去 + 回」。想一想为什么把边反向再跑一次 Dijkstra 就能拿到「回」的距离。

本课小结

• 两个动作：松弛（if (dis[u] + w < dis[v]) 就更新）+ 盖章（每轮挑 dis 最小的未定点）。
• 敢盖章的理由：边权非负 ⇒ 绕路只会更贵 ⇒ 此刻最小的点不可能被超越（反证三行）。
• 朴素版 O(n²)：n = 105、m = 2×105 时 30.2 秒，过不了 P4779（时限 1000 ms）。
• 堆优化 O(m log m)：同一张图 9.1 ms；靠 priority_queue 小根堆 + 懒删除 if (du > dis[u]) continue;。
• 常见失分点：不判不可达、忘了 dis[s]=0、不关流同步白白多花 300 ms、拿它去跑负权图。