最短路：Dijkstra 与 01-BFS

前言

上一篇我们用 BFS 解决了无权图的最短路——“每条边都是一步”。但现实中的路不是等长的：从北京到上海坐高铁 4 小时，坐大巴 12 小时。如果只算”经过几条路”，大巴和高铁都是”1 步”——这显然不合理。

加权图中，每条边有一个权值（距离、时间、费用）。我们要找的不再是”经过最少条边”，而是”总权值最小”的路径。BFS 的”先发现 = 更近”假设在加权图上彻底失效了——一条权 100 的边和一条权 1 的边，在 BFS 眼里都是”1 步”。

Dijkstra 算法修正了这个假设：不再按”发现的先后”处理，而是每次从所有未确定节点中选距离最小的那个。这个看似微小的改变，让算法从”无权”跳到了”非负权”。

教材（Tessoku Book 9.4 B64 Shortest Path）不仅讲解了 Dijkstra 求最短距离，还展示了路径还原——从终点倒推回去，找到具体走了哪些边。

问题的本质

为什么 BFS 在加权图上会出错？

一个简单的反例：起点 1 连到 2（权 100）和 3（权 1），3 连到 2（权 1）。

• BFS 先发现 2（通过边 1→2），设 $dist[2] = 100$。后来发现 1→3→2 总距离 2，但 BFS 不会”反悔”——已经设了 $dist[2]$ 就不改了。
• Dijkstra 先处理 3（距离 1 比 2 的 100 小），然后通过 3 更新 $dist[2] = 2$。允许”反悔”。

这就是 Dijkstra 的核心修正：每次选距离最小的未确定节点，用它去更新邻居。如果发现了更短的路径，就更新。

Dijkstra 的贪心为什么是对的？

关键假设：所有边权非负。

Dijkstra 每次从”当前距离最小的未确定节点” $u$ 出发，用它的边去松弛邻居。为什么一旦 $u$ 被选中，$dist[u]$ 就一定是最短距离？

反证法：假设存在一条更短的路径到 $u$，长度为 $d' < dist[u]$。这条路径一定经过某个未确定的节点 $v$（否则路径上的所有节点都已确定，$dist[u]$ 应该已经被正确更新了）。但 $dist[v] \ge dist[u]$（因为 $u$ 是距离最小的未确定节点），而 $v$ 到 $u$ 的边权 $\ge 0$，所以经过 $v$ 的路径长度 $\ge dist[v] \ge dist[u] > d'$——矛盾！

所以 $dist[u]$ 一定已经是最短距离，不会后悔。

如果边权有负数呢？

上面的论证在边权为负时不成立——$v$ 到 $u$ 的边权可能是 $-100$，经过 $v$ 的路径确实可能比 $dist[u]$ 更短。Dijkstra 的贪心选择不再正确。下一篇的 Bellman-Ford 专门解决这个问题，代价是更慢的时间复杂度。

01-BFS：边权只有 0 和 1 时的优化

如果边权只有 0 和 1，不需要 $O(\log N)$ 的优先队列。用一个双端队列（deque）：

• 边权为 0：加到队头（不增加距离，应该优先处理）
• 边权为 1：加到队尾

为什么队头始终距离最小？ 因为权 0 的边加到队头，等于”和当前节点同等距离”。权 1 的边加到队尾，等于”比当前节点距离大 1”。队头到队尾距离递增——和优先队列的排序效果一样，但每次操作 $O(1)$。

总时间复杂度 $O(N + M)$，比 Dijkstra 的 $O((N+M) \log N)$ 更快。这是竞赛中的一个常见优化——边权只有 0/1 时，总是用 01-BFS 代替 Dijkstra。

教材的路径还原技巧

教材 9.4 B64 教了一种优雅的路径还原方法：从终点 $N$ 倒推。对于节点 $v$ 的每个邻居 $u$，检查 $dist[u] + w(u,v) = dist[v]$ 是否成立——如果成立，说明最短路经过了 $u \to v$ 这条边。把 $u$ 加入路径，继续倒推，直到回到起点。

理论 + 代码

Dijkstra

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;
const ll INF = 1e18;
const int MAXN = 100006;

vector<pair<int,int>> adj[MAXN]; // adj[u] = {(v, weight)}
ll dist[MAXN];

void dijkstra(int start, int N) {
    for (int i = 1; i <= N; i++) dist[i] = INF;
    dist[start] = 0;
    priority_queue<pli, vector<pli>, greater<pli>> pq; // ① 小根堆
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop(); // ② 取距离最小的
        if (d > dist[u]) continue;         // ③ 过期数据，跳过
        for (auto [v, w] : adj[u]) {       // ④ 遍历邻居
            if (dist[v] > dist[u] + w) {   // ⑤ 松弛
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});      // ⑥ 入队
            }
        }
    }
}

逐行解析：

• ① greater<pli> 使优先队列变成小根堆——堆顶是距离最小的节点。为什么用小根堆而不是大根堆？因为我们要每次取距离最小的未确定节点，小根堆的 top() 就是这个节点。
• ② 取出距离最小的未确定节点。这就是 Dijkstra 的”贪心选择”。
• ③ 关键优化：同一个节点可能被多次入队（每次松弛都入队）。只有第一次弹出的是最新距离，后续弹出的都是”过期数据”——$d$ 比 $dist[u]$ 大，说明 $dist[u]$ 已经被更短的路径更新过了。这个技巧叫 lazy deletion，避免了从堆中删除元素（堆不支持高效删除）。教材用 kakutei[] 布尔数组实现同样的效果——标记已确定的节点，弹出后直接跳过。
• ⑤ 松弛操作：如果经过 $u$ 到 $v$ 更短，就更新。这就是 Dijkstra 的”反悔”——和 BFS 不同，Dijkstra 允许后续发现更短的路径。
• 时间复杂度 $O((N+M) \log N)$。瓶颈在堆操作，每条边最多导致一次入堆。

路径还原（教材方法）

vector<int> restore_path(int N) {
    vector<int> path;
    int pos = N;                               // ① 从终点开始
    while (true) {
        path.push_back(pos);
        if (pos == 1) break;                   // ② 到达起点
        for (auto [nxt, cost] : adj[pos]) {
            if (dist[nxt] + cost == dist[pos]) { // ③ 找前驱
                pos = nxt;
                break;
            }
        }
    }
    reverse(path.begin(), path.end());
    return path;
}

逐行解析：

• ① 从终点倒推——为什么能这样做？因为如果最短路经过 $u \to v$，那么 $dist[u] + w(u,v) = dist[v]$，所以检查每条边就能找到前驱。
• ③ 检查邻居 $nxt$：如果 $dist[nxt] + cost = dist[pos]$，说明最短路经过了 $nxt \to pos$。

01-BFS

#include <deque>
void bfs01(int start, int N) {
    for (int i = 1; i <= N; i++) dist[i] = INF;
    dist[start] = 0;
    deque<int> dq;
    dq.push_back(start);
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v); // ① 权 0 → 队头
                else         dq.push_back(v);  // ② 权 1 → 队尾
            }
        }
    }
}

逐行解析：

• ① 权 0 的边不增加距离，所以加到队头——和当前节点同等优先级，应该尽早处理。
• ② 权 1 的边增加距离 1，加到队尾——比当前节点距离大 1，后处理。

模拟走一遍

图：1-2(2), 1-3(5), 2-3(1), 2-4(6), 3-4(2)。起点 1。

步骤	取出	dist[1]	dist[2]	dist[3]	dist[4]	堆内容
初始	—	0	∞	∞	∞	{(0,1)}
1	1	0	2	5	∞	{(2,2),(5,3)}
2	2	0	2	3	8	{(3,3),(5,3),(8,4)}
3	3	0	2	3	5	{(5,3过期),(8,4过期),(5,4)}
4	4	0	2	3	5	空

最终 dist = [0, 2, 3, 5]。路径 1→2→3→4 = 2+1+2 = 5。

注意步骤 3：弹出 (5,3) 时 5 > dist[3]=3，这是过期数据，跳过。这就是 lazy deletion——堆里有多个 3 的记录，但只有第一个（距离 3 的那个）是有效的。

例题

例题 1：TB A64 — Shortest Path 2

题目：$N$ 个顶点 $M$ 条边的加权无向图。求顶点 1 到所有顶点的最短距离。不可达输出 -1。

数据范围：$2 \le N \le 10^5$，$1 \le M \le 10^5$，$1 \le C_i \le 10000$

—— AtCoder Tessoku Book A64

分析：裸的 Dijkstra 模板题。

代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;
const ll INF = 1e18;
const int MAXN = 100006;

vector<pair<int,int>> adj[MAXN];
ll dist[MAXN];

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    for (int i = 1; i <= N; i++) dist[i] = INF;
    dist[1] = 0;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop(); // ① 取距离最小
        if (d > dist[u]) continue;         // ② 过期数据
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {   // ③ 松弛
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int i = 1; i <= N; i++)
        printf("%lld\n", dist[i] == INF ? -1 : dist[i]);
    return 0;
}

逐行解析：

• ①②③ 标准 Dijkstra 三板斧：取最小、过滤过期、松弛。
• 答案不可达的输出 -1。

---

例题 2：TB B64 — Shortest Path with Restoration

题目：和例题 1 一样，但还要输出从顶点 1 到每个顶点的最短路径（经过的顶点列表）。

—— AtCoder Tessoku Book B64

分析：加一个 prev 数组记录最短路径上的前驱节点。

代码：

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;
const ll INF = 1e18;
const int MAXN = 100006;

vector<pair<int,int>> adj[MAXN];
ll dist[MAXN];
int prev_node[MAXN];

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    for (int i = 1; i <= N; i++) dist[i] = INF;
    dist[1] = 0;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                prev_node[v] = u;       // ① 记录前驱
                pq.push({dist[v], v});
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        if (dist[i] == INF) { printf("-1\n"); continue; }
        // ② 回溯路径
        vector<int> path;
        for (int x = i; x != 0; x = prev_node[x]) path.push_back(x);
        for (int j = path.size() - 1; j >= 0; j--)
            printf("%d%c", path[j], " \n"[j == 0]);
    }
    return 0;
}

逐行解析：

• ① 每次松弛时记录 prev_node[v] = u，表示最短路径上 $v$ 的前一个节点是 $u$。
• ② 从终点沿 prev_node 回溯到起点，得到完整路径。反转输出。

---

例题 3：M&A 048 — Small Multiple

题目：给定整数 $K$（$2 \le K \le 10^5$），求 $K$ 的正整数倍中，各位数字之和的最小值。

—— AtCoder M&A 048

分析：01-BFS 经典题。在模 $K$ 的意义下建图：

• 从状态 $x$（模 $K$ 余数），操作 ×10 到达 $(x \times 10) \bmod K$，代价为 0
• 从状态 $x$，操作 +1 到达 $(x + 1) \bmod K$，代价为 1

为什么这样建模？考虑数字 $x$ 的各位数字之和 $s(x)$。如果 $x \to x \times 10$，各位和不变（比如 12→120，各位和都是 3）。如果 $x \to x+1$，各位和最多变化 1（比如 12→13 各位和 3→4，但 19→20 各位和 10→2）。

但 01-BFS 的代价不代表各位和的精确变化量。实际上，dist[v] 的含义是”从 1 出发，到达模 $K$ 为 $v$ 的状态，所经过的最少 +1 操作次数”。而 dist[1 % K] = 1 表示初始数字 1 本身就贡献了各位和 1（可以理解为：数字 1 的各位和 = 1，不经过任何 +1 操作，但起始贡献为 1）。

直觉上：乘 10 是”免费”的（各位和不增加），加 1 是”花钱”的。从数字 1 开始，尽可能多用免费操作，少用花钱操作，到达 $K$ 的倍数时花的钱最少 = 各位和最小。

代码：

#include <cstdio>
#include <deque>
#include <cstring>
using namespace std;

const int MAXN = 100006;
int dist[MAXN];

int main() {
    int K;
    scanf("%d", &K);
    memset(dist, -1, sizeof(dist));
    deque<int> dq;
    dist[1 % K] = 1;         // ① 起始状态：数字 1 的各位和 = 1
    dq.push_back(1 % K);
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        // ② 操作 ×10：代价 0
        int v10 = (u * 10) % K;
        if (dist[v10] == -1 || dist[v10] > dist[u]) {
            dist[v10] = dist[u];
            dq.push_front(v10); // 代价 0 → 队头
        }
        // ③ 操作 +1：代价 1
        int v1 = (u + 1) % K;
        if (dist[v1] == -1 || dist[v1] > dist[u] + 1) {
            dist[v1] = dist[u] + 1;
            dq.push_back(v1);  // 代价 1 → 队尾
        }
    }
    printf("%d\n", dist[0]);   // ④ 模 K 为 0 时即为 K 的倍数
    return 0;
}

逐行解析：

• ① 从数字 1 开始，各位和 = 1。
• ② ×10 不改变各位和（比如 12→120，各位和不变），代价 0。
• ③ +1 可能增加各位和 1（比如 12→13），代价 1。
• ④ 模 $K$ 为 0 的状态代表 $K$ 的倍数，其距离就是最小各位和。

验证：$K=6$。数字 1→2→3→4→5→6(=6×1)。各位和最小 = 1+2=3（12=6×2）。✓

---

例题 4：T90 013 — Passing（★5）

题目：$N$ 个城镇 $M$ 条加权无向边。对每个 $k$，求从城镇 1 经过城镇 $k$ 再到城镇 $N$ 的最短时间。

数据范围：$2 \le N \le 10^5$

—— AtCoder Typical 90 013

分析：答案 = $dist_1[k] + dist_N[k]$。跑两次 Dijkstra：一次从 1，一次从 N。

代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;
const ll INF = 1e18;
const int MAXN = 100006;

vector<pair<int,int>> adj[MAXN];
ll dist1[MAXN], distN[MAXN];

void dijkstra(int start, ll dist[], int N) {
    for (int i = 1; i <= N; i++) dist[i] = INF;
    dist[start] = 0;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    dijkstra(1, dist1, N);    // ① 从 1 出发
    dijkstra(N, distN, N);    // ② 从 N 出发
    for (int k = 1; k <= N; k++)
        printf("%lld\n", dist1[k] + distN[k]); // ③ 经过 k 的最短路
    return 0;
}

逐行解析：

• ①② 跑两次 Dijkstra：一次从 1 出发，一次从 N 出发。
• ③ 经过 $k$ 的最短路 = 从 1 到 $k$ 的最短路 + 从 $k$ 到 $N$ 的最短路 = $dist_1[k] + dist_N[k]$。
• 总时间 $O((N+M) \log N)$。

---

例题 5：T90 043 — Maze Challenge with Lack of Sleep（★4）

题目：$H \times W$ 网格迷宫。从起点到终点，求最少转弯次数（改变移动方向的次数）。

数据范围：$2 \le H, W \le 1000$

—— AtCoder Typical 90 043

分析：01-BFS 的经典应用。继续沿当前方向走代价 0，转弯代价 1。把”方向+位置”作为状态。

代码：

#include <cstdio>
#include <deque>
#include <cstring>
using namespace std;

const int MAXN = 1006;
char grid[MAXN][MAXN];
int dist[MAXN][MAXN][4]; // ① dist[r][c][dir]：在(r,c)面朝dir时的最少转弯数
int H, W;
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};

int main() {
    int sr, sc, tr, tc;
    scanf("%d%d%d%d%d%d", &H, &W, &sr, &sc, &tr, &tc);
    for (int i = 1; i <= H; i++) scanf("%s", grid[i] + 1);

    memset(dist, -1, sizeof(dist));
    deque<tuple<int,int,int>> dq;
    for (int d = 0; d < 4; d++) {
        dist[sr][sc][d] = 0;
        dq.push_back({sr, sc, d}); // ② 起点四个方向都入队
    }
    while (!dq.empty()) {
        auto [r, c, dir] = dq.front(); dq.pop_front();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 1 || nr > H || nc < 1 || nc > W) continue;
            if (grid[nr][nc] == '#') continue;
            int cost = (d == dir) ? 0 : 1; // ③ 同方向代价0，转弯代价1
            if (dist[nr][nc][d] == -1 || dist[nr][nc][d] > dist[r][c][dir] + cost) {
                dist[nr][nc][d] = dist[r][c][dir] + cost;
                if (cost == 0) dq.push_front({nr, nc, d}); // ④ 代价0→队头
                else           dq.push_back({nr, nc, d});  // ⑤ 代价1→队尾
            }
        }
    }
    int ans = 1e9;
    for (int d = 0; d < 4; d++)
        if (dist[tr][tc][d] != -1) ans = min(ans, dist[tr][tc][d]);
    printf("%d\n", ans);
    return 0;
}

逐行解析：

• ① 状态是 (行, 列, 当前方向)。转弯 = 改变方向，代价 1；继续同方向，代价 0。
• ③ 关键：和当前方向相同则代价 0，否则代价 1。
• ④⑤ 01-BFS：代价 0 放队头，代价 1 放队尾。

参考文献

教材讲解 — 競技プログラミングの鉄則 第 9 章

• 9.4 Dijkstra 法 + 路径还原（B64 Shortest Path 解说）

基础练习 — アルゴリズムと数学 演習問題集

• 048 Small Multiple（01-BFS）【例题】

系统练习 — 競技プログラミングの鉄則

• A64 Shortest Path 2（Dijkstra 模板）【例题】
• B64 Shortest Path with Restoration（路径还原）【例题】

实战练习 — 競プロ典型 90 問

• 013 Passing（★5，双向 Dijkstra）【例题】
• 043 Maze Challenge with Lack of Sleep（★4，01-BFS）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化