🌊

Dijkstra：水波纹一圈圈扩出去

从 1 号岛出发，到每个岛最短路有多长？水波纹从 1 号岛荡开：波纹每到一个岛，那个岛的最短路就「盖章确认」——因为边权非负，后到的波纹不可能更短。

💡 打个比方

往池塘中心（1 号岛）扔一颗石子，水波纹一圈圈向外荡。波纹以「桥的造价」为单位速度扩散：先碰到 2 号岛（造价 2），再碰到 3 号岛（经 2，2+3 = 5）……波纹第一次到达某个岛时，走的就是最短路——为什么？因为所有桥造价都 ≥ 0：绕远路只会累加，不可能变便宜。所以「第一次到 = 最短」，到过的岛就盖章确认，不再改。

先问一个容易搞混的问题：这不是七级学过的 BFS（层数最少的搜索）吗？不一样！BFS 假设每步成本相同（边权都是 1），数「层数/跳数」就行；现在每座桥造价不同（2、3、4、5、6、7、8），跳数少 ≠ 路程短：1→3 直接 1 跳造价 6，走 1→2→3 是 2 跳但造价 2+3 = 5 < 6——「2 跳」反而更短！所以必须累加造价，不能数跳数：这就是「带权最短路」，算法叫 Dijkstra（迪杰斯特拉，1956）。

Dijkstra 和 Prim 长得像（都是「选最小 + 更新邻居」），但目标不同：Prim 维护「接进树最便宜的一条边」（dist 只存边权），Dijkstra 维护「从起点到该点的整条路总造价」（dist 存累计距离，更新公式是 dist[v] = min(dist[v], dist[u] + w)——叫松弛）。

流程：① dist[起点] = 0，其余 = ∞；② 每轮在未确认的点里选 dist 最小的「盖章」（确认它的最短路）；③ 用它松弛所有邻居（经它走更便宜就更新）；④ 直到所有点都盖章。波纹荡完，每个岛的最短路都在账本上。

术语：单源最短路（从一个起点到所有点的最短距离）；dist[]（起点到每点的最短距离账本）；done[]/确认（该点最短路已盖章，不再改）；松弛（dist[v] = min(dist[v], dist[u] + w)：发现更短的路就「放松」旧记录）；非负权（所有边权 ≥ 0，Dijkstra 生效的前提）；最短路树（从起点出发的所有最短路拼成的树）。

🖼️ 大图看明白

🧩 子任务 1：最短路问题——跳数少 ≠ 路程短

🎯 小目标：明白「带权最短路」为什么不能用 BFS 数层数，会手算「直达 vs 绕路」谁更短。

七级的 BFS 数的是跳数（几层到），默认每步成本一样。现在每座桥造价不同，「路程」= 沿路造价累加。还是 5 岛 7 桥，看一个反直觉的例子：

// 从 1 到 3，两条路：
// 路 A（直达）：1 → 3，造价 6，跳数 1
// 路 B（绕 2）：1 → 2 → 3，造价 2 + 3 = 5，跳数 2

// BFS（数跳数）会说：路 A 只要 1 跳，更「近」！
// 但按造价：5 < 6 —— 2 跳的路 B 反而更短！

// 再看 1 到 4：
// 路 C：1 → 2 → 4，造价 2 + 7 = 9，跳数 2
// 路 D：1 → 2 → 3 → 4，造价 2 + 3 + 4 = 9，跳数 3
// 造价打平（9 = 9）——跳数多不代表更贵，「层数」彻底失准

// 再看 1 到 5：
// 路 E（直达）：1 → 5，造价 8，跳数 1
// 路 F（绕远）：1 → 2 → 3 → 4 → 5，造价 2+3+4+5 = 14，跳数 4
// 这次直达赢（8 < 14）——但赢是因为造价，不是因为跳数

// 结论：边权不同时，最短路 = 「造价累加最小」，
// 必须逐点算「起点到它的最短总造价」——这就是单源最短路问题。

✅ 小检查：① 从 1 到 3，BFS 会报几跳？按造价最短路是几、走哪条？② 为什么「跳数少」不能保证「造价低」？③ 如果所有桥造价都是 1，BFS 的层数还能当最短路吗？

看看答案

① BFS 报 1 跳（直达 1-3）；按造价最短路是 5，走 1→2→3（2 跳）——BFS 的答案「1 跳 = 造价 6」根本不是最短。② 跳数只数「经过几条边」，不管每条边多贵：1 跳的边可能造价 100，3 跳的边可能每跳 1——跳数和造价是两套账，边权不同时跳数失准。③ 能！边权全为 1 时，造价 = 跳数，「跳数最少」就是「造价最低」，BFS 恰好就是最短路算法（七级学的正是这种特例）。

易错：看到「最短路」就条件反射写 BFS——BFS 只对边权全相同（尤其全 1）的图成立。图里一旦有「造价 2、3、4…」，就必须用带权算法（Dijkstra / Floyd）。先问一句：「边权一样吗？」

🧩 子任务 2：Dijkstra 手推——波纹盖章 4 轮

🎯 小目标：完整手推 Dijkstra（dist 初始化 → 每轮「确认最小 + 松弛邻居」），会边推边更新 dist 账本。

还是 5 岛 7 桥，起点 1。Dijkstra 账本：dist[i] = 目前已知「1 到 i」的最短造价；每轮在未确认的点里选 dist 最小的盖章（它的最短路定案），再用它松弛邻居（经它走更便宜就更新 dist）：

// 初始：dist[1] = 0（起点到自己免费），其余 = ∞；确认集 = 空
// 用起点 1 松弛它的邻居（1-2:2、1-3:6、1-5:8）：
dist: 1=0  2=2  3=6  4=∞  5=8

// 轮 1：未确认里 dist 最小 = 2（造价 2）→ 盖章 2！
// 松弛 2 的邻居（公式：dist[v] = min(dist[v], dist[2] + 边权)）：
//   2-3: dist[3] = min(6, 2 + 3) = min(6, 5) = 5 ✓ 更新（绕 2 更便宜）
//   2-4: dist[4] = min(∞, 2 + 7) = min(∞, 9) = 9 ✓ 更新（第一次够到 4）
dist: 2=2（已确认） 3=5  4=9  5=8

// 轮 2：未确认最小 = 3（5）→ 盖章 3！
// 松弛 3 的邻居：3-4: dist[4] = min(9, 5 + 4) = min(9, 9) = 9（打平，不变）
dist: 3=5（已确认） 4=9  5=8

// 轮 3：未确认最小 = 5（8）→ 盖章 5！
// 松弛 5 的邻居：4-5: dist[4] = min(9, 8 + 5) = min(9, 13) = 9（不变）
dist: 5=8（已确认） 4=9

// 轮 4：未确认只剩 4（9）→ 盖章 4！无未确认邻居，结束

// 最终答案（1 到各岛最短路）：
// 1→2 = 2（直达）；1→3 = 5（经 2）；1→4 = 9（经 2、3 或经 2 直达，都是 9）
// 1→5 = 8（直达，比绕路 14 便宜）

✅ 小检查：① 轮 2 松弛 3-4 时，min(9, 5+4) 为什么「不变」？② 盖章顺序是 2、3、5、4——为什么 5（造价 8）比 4（造价 9）先盖章？③ 1→4 的 9 有几种走法？分别是什么？

看看答案

① 5 + 4 = 9，和旧值 9 打平——「更便宜才更新」，打平不算更便宜，所以不变（其实走 1→2→3→4 和 1→2→4 一样短，程序不关心，只记数字 9）。② 盖章比的是 dist（起点到它的总造价），不是它身上某条边的造价：5 的 dist = 8（直达），4 的 dist = 9（要绕）——8 < 9，所以 5 先盖章。「波纹先到 5 号岛」。③ 两种：1→2→4（2+7 = 9）和 1→2→3→4（2+3+4 = 9）。dist 只存数字 9，不存路线；要路线得另存「前驱」（下一课 Floyd 会碰到类似的事）。

易错：松弛时写成 dist[v] = dist[u] + w（无脑覆盖）——会把更短的旧记录冲掉（比如 dist[4] 已经是 9，却用 8+5 = 13 覆盖成 13）。必须是 min：新路更短才换，否则保留旧记录。

🧩 子任务 3：为什么「盖章了就不能再变」

🎯 小目标：会用「非负权 → 绕远只加不减」论证盖章的正确性，会举负权反例说明它为何失效。

Dijkstra 敢「一次定案」，靠的是边权非负。把波纹论证写完整：

// 波纹论证（为什么盖章 u 后，dist[u] 不会再被打破）：
// 假设还存在一条更短的路到 u。u 已盖章，这条新路必然
// 「经过某个还没盖章的岛 x」再走到 u：
//   新路造价 = (1 到 x 的造价) + (x 走到 u 的造价)
// 关键：x 走到 u 这一段，每座桥造价 ≥ 0 → 这段造价 ≥ 0
//   → 新路造价 ≥ (1 到 x 的造价) = dist[x]
// 而盖章 u 时，u 是「未确认里 dist 最小」的 → dist[x] ≥ dist[u]
//   → 新路造价 ≥ dist[x] ≥ dist[u] —— 绕远不可能更短！✓
// 一句话：非负权 → 路越走造价只「加」不「减」→ 先到即最短。

// 负权为什么打破原则（反例，3 岛）：
// 桥：1→2 造价 1；1→3 造价 2；3→2 造价 −5（「反向收费」）
// Dijkstra 过程：初始 dist[2]=1, dist[3]=2
//   轮 1：盖章 2（1 < 2）—— 定案 dist[2] = 1
// 但真相：1 → 3 → 2 = 2 + (−5) = −3 < 1 ！
// 「绕远」（经 3）反而更便宜 —— 负权 = 越走越便宜，
// 「每段 ≥ 0」的波纹论证塌了 → 盖章错定案 → Dijkstra 出错。
// 结论：Dijkstra 只保证「非负权」正确；有负权要换算法
//（下一课 Floyd 能吃负权，但不能吃「负权圈」）。

✅ 小检查：① 论证里「dist[x] ≥ dist[u]」为什么成立？② 反例里 1→2 的真正最短路是多少？走哪？③ 若 3→2 的造价是 −1（不是 −5），Dijkstra 还对吗？为什么？

看看答案

① 盖章 u 的那一刻，u 是所有未确认点里 dist 最小的；x 那时还没盖章（否则新路就不用「经 x」了），所以 x 在「未确认」名单里 → dist[x] ≥ dist[u]。② 1 → 3 → 2 = 2 + (−5) = −3（比直达的 1 便宜 4）——负权桥把「绕路」变成了「省钱捷径」。③ 1 → 3 → 2 = 2 + (−1) = 1，和直达的 1 打平——Dijkstra 报 1，恰好没报错过（「运气好」的情况）；但只要存在更短绕路（如 −5 例），就会错。所以「非负」是保险，不是「有时够」。

易错：图里有负权桥还硬上 Dijkstra——「盖章定案」会错。用 Dijkstra 前先检查：所有边权 ≥ 0 吗？不是就换 Floyd（或学过的 SPFA，本课不展开）。

🧩 子任务 4：松弛操作——dist[v] = min(dist[v], dist[u] + w)

🎯 小目标：会写松弛的代码（更便宜才更新），会逐行推「盖章 → 松弛邻居」的更新表。

「松弛」是所有最短路算法的基本动作：每盖章一个点 u，就问它的每个邻居 v：「经过 u 到你，比现在记录的路更便宜吗？」便宜就更新（「放松」旧记录），不便宜就保留：

// 松弛公式（u 已盖章，v 是 u 的邻居，w = 桥 (u,v) 的造价）：
//   dist[v] = min(dist[v], dist[u] + w)
//   左边 = 现有记录（1 → v 目前已知最短）
//   右边 = 「1 → u（已定案）+ 桥 u→v」这条新路的造价
//   min = 谁便宜要谁 —— 只有新路更短才「放松」记录

// 代码（邻接矩阵 g，done[] 是盖章标记）：
if (g[u][v] > 0) {                    // u、v 之间有桥
    if (!done[v] && dist[v] > dist[u] + g[u][v])
        dist[v] = dist[u] + g[u][v];  // 发现更短的路 → 松弛
}

// 松弛推演表（本课 5 岛图，逐盖章记录）：
// 盖章 2（dist = 2）：
//   v = 3：6 > 2 + 3 = 5？ 是 → dist[3] = 5
//   v = 4：∞ > 2 + 7 = 9？ 是 → dist[4] = 9
//   v = 1：已盖章 → 跳过
// 盖章 3（dist = 5）：
//   v = 4：9 > 5 + 4 = 9？ 否（打平）→ 不变
//   v = 1、2：已盖章 → 跳过
// 盖章 5（dist = 8）：
//   v = 4：9 > 8 + 5 = 13？ 否 → 不变
// 盖章 4（dist = 9）：v = 5 已盖章 → 无更新，结束

✅ 小检查：① 松弛判断为什么写 dist[v] > dist[u] + w（而不是 ≥）？② 如果写成 ≥ 会怎样？（数字答案变不变？）③ 松弛的两个前提条件（!done[v] 和 g[u][v] > 0）各防什么错？

看看答案

① > 表示「严格更便宜才更新」：打平（=）时旧记录和新路一样短，保留旧的即可。② 用 ≥ 的话，打平时也会把 dist[v] 重写成同一个数——数字答案不变（9 还是 9），但若程序还记录「走哪条路」（前驱），会无谓地改写路线；用 > 更干净稳定。③ !done[v]：已盖章的 v 已经定案，再松弛它可能破坏定案（负权图里尤其危险；非负权里也不会变小，但白算）；g[u][v] > 0：0 表示「没桥」，不检查就会把「没桥」当成造价 0 的免费桥（dist[u] + 0 可能错误地更小）。

易错：松弛漏写 min（直接 dist[v] = dist[u] + g[u][v] 无脑覆盖）——「打平或更贵」的新路也会把更短的旧记录冲掉（如 dist[4] 已是 9，被 8+5 = 13 覆盖）。记住：更便宜才换，否则保留。

💻 完整代码：Dijkstra（5 点邻接矩阵）→ 输出 1 到各点最短路

// 输入：无（5 岛 7 桥写死，方便对答案）
// 输出：1 到每个点的最短路长度
// 答案：1→1=0，1→2=2，1→3=5，1→4=9，1→5=8
#include <iostream>
using namespace std;

int g[6][6];     // 邻接矩阵：g[i][j] = 桥造价，0 = 没桥
int dist_[6];    // 从 1 到点 i 的当前最短路（账本）
bool done_[6];   // 点 i 是否已盖章（定案）

int main() {
    // 5 岛 7 桥：1-2:2  2-3:3  3-4:4  4-5:5  1-3:6  2-4:7  1-5:8
    g[1][2] = g[2][1] = 2;  g[2][3] = g[3][2] = 3;
    g[3][4] = g[4][3] = 4;  g[4][5] = g[5][4] = 5;
    g[1][3] = g[3][1] = 6;  g[2][4] = g[4][2] = 7;
    g[1][5] = g[5][1] = 8;

    const int INF = 999999;
    for (int i = 1; i <= 5; i++) { dist_[i] = INF; done_[i] = false; }
    dist_[1] = 0;
    for (int v = 1; v <= 5; v++)                // 账本初始化：1 的桥给出初始报价
        if (g[1][v] > 0) dist_[v] = g[1][v];

    for (int round = 1; round <= 5; round++) {
        // ① 未确认里找 dist 最小的点 u，盖章（非负权 → 定案不再变）
        int u = 0;
        for (int i = 1; i <= 5; i++)
            if (!done_[i] && (u == 0 || dist_[i] < dist_[u])) u = i;
        done_[u] = true;

        // ② 水波纹：松弛 u 的邻居（更便宜才换记录）
        for (int v = 1; v <= 5; v++)
            if (g[u][v] > 0 && !done_[v] && dist_[v] > dist_[u] + g[u][v])
                dist_[v] = dist_[u] + g[u][v];
    }

    for (int i = 1; i <= 5; i++)
        cout << "1 到 " << i << " 最短路 = " << dist_[i] << endl;
    return 0;
}
// 运行结果：1 到 1 = 0，1 到 2 = 2，1 到 3 = 5，1 到 4 = 9，1 到 5 = 8
// 盖章顺序：1 → 2 → 3 → 5 → 4（dist 从小到大：0、2、5、8、9）
// 把 g[2][4] 改成 1：1→4 = 3（经 1-2-4），盖章顺序变为 1 → 2 → 4 → 3 → 5

✋ 你来试试

第 1 题：把 2-4 造价改成 1，1→4 最短路是多少？盖章顺序怎么变？

账本初始：dist[2]=2、dist[3]=6、dist[4]=∞、dist[5]=8。盖章 2（2）后松弛：dist[3] = min(6, 2+3) = 5、dist[4] = min(∞, 2+1) = 3。下一轮未确认里最小的是 4（3），盖章 4；松弛 4-5：8 与 3+5=8 打平，不变。接着盖章 3（5）、5（8）。所以 1→4 = 3（走 1→2→4），盖章顺序变成 1 → 2 → 4 → 3 → 5——「经 2 直达 4」比绕 3 便宜了 6。

第 2 题：想让程序输出「1→2→3」这样的路线而不只是数字，要加什么表？

加一张prev[] 前驱表：每次松弛把 dist[v] 更新成更小的值时，同时记下 prev[v] = u（「v 的最短路是经由 u 来的」）。结束时从目标点倒着走：目标 → prev[目标] → prev[prev[目标]] → … → 1，再反一下就是完整路线。就像快递单上「上一站是谁」，从终点一路问回去。

第 3 题：本图「1 到各点最短路之和」= 2+5+9+8 = 24，和 MST 总造价 14 有什么关系？

它们是两个不同的问题，数字没有换算关系：MST 让「桥的总造价」最小——挑 n−1 = 4 座桥把所有岛连起来（14）；最短路让「从 1 出发到每个点的路」各自最短（24），每条路可以重复使用已经修好的桥，而且只关心「从 1 走」这一个起点。同一个 5 岛图，Kruskal/Prim 报 14，Dijkstra 报 2+5+9+8 = 24，都对。

第 4 题（加餐）：负权反例（1→2:1、1→3:2、3→2:−5）里，Dijkstra 错在哪一步？

错在「盖章定案」那一步：第 1 轮未确认里 dist[2]=1 < dist[3]=2，程序先给 2 盖章、宣布「1→2 = 1 定案」；但真正的最短路 1→3→2 = 2+(−5) = −3，要「经过还没盖章的 3」绕一圈回来翻案——可 2 已经盖章，程序再也不会改它了。病根：非负权保证「绕远只会加不会减」，−5 这座负权桥把这条铁律打破了。所以 Dijkstra 的说明书上写着：边权必须非负。

🎯 一句话记住：Dijkstra = 水波纹——每轮「未确认里 dist 最小者盖章（非负权 → 定案）+ 松弛邻居 dist[v] = min(dist[v], dist[u]+w)」；BFS 只在边权全 1 时才等于最短路；本课答案 1→2=2、1→3=5（经 2）、1→4=9、1→5=8，盖章顺序 1→2→3→5→4。

← 上一课：09 最小生成树 Prim 下一课：11 Floyd 全源最短路 →