本讲定位：图论系列第五讲，最短路四讲的第一讲。第 02、03 讲的 BFS 只能处理”边权全相等”（以及 01-BFS 那种”只有两种取值”）的图；一旦每条边有各自的长度，队列的”先进先出”就不再等于”距离从小到大”，那个归纳证明当场崩塌。修复办法只有一句话：把队列换成优先队列，每次取出当前距离最小的点——这就是 Dijkstra。本讲做了六组实测：三种实现与 Floyd 逐点对拍 8000 组全部一致；朴素 $O(n^2)$ 在 P4779 的数据上限（$n=10^5$）要 24.96 秒，堆优化只要 0.0205 秒（1218 倍）；但流传的”稠密图上朴素反而更快”在邻接表下并不成立——完全图上堆优化仍快 1.5 倍，原因是入堆次数只占 $m$ 的 0.22%，朴素版真正的主场是”图以邻接矩阵给出”（实测快 5 倍且省 69 MB）；漏写
if (d > dis[u]) continue;在稀疏图上几乎无代价、在稠密图上多扫 6.02 倍的边、慢 4 倍；dis初值用INT_MAX且漏写保护时错 88.3%，用0x3f3f3f3f则 0%；负权反例最小 3 个点 3 条边（只需一条负边），而且三种常见写法在负权下的表现互不相同——这是本讲最值得记住的一张表。文中所有代码经g++ -O2 -std=c++14 -Wall编译运行，P3371、P4779 与洛谷官方样例核对通过。前置知识：第 01 讲的
vector邻接表；第 02 讲的 BFS 与”层数即无权最短路”的证明（本讲从推翻它的前提开始）；priority_queue的基本用法（见csps-series/csps-stl-containers.md第 5 节，那里从容器的角度讲了同一份代码，本讲从算法的角度讲）。不需要第 03、04 讲。适合对象：全讲标 J，是 CSP-J 复赛的必备算法，也是 CSP-S 一切最短路题的底座。第 6 节（负权）标 J⭐，它本身不难，但它是第 06 讲存在的全部理由，不要跳。
第 02 讲证明了：无权图上 BFS 的层数就是最短路。证明的核心是那个不变量——
队列里的点的
dis从队首到队尾非降，且极差 $\le 1$。
这个不变量唯一依赖的前提是”每条边长度恰好为 1”。现在把边权换成任意正整数，看会发生什么：
2 1
1 ───────→ 2 ─────→ 3
│ ↑
└────────────────────┘
10
BFS 从 1 出发：把 2 和 3 一起入队（都是第 1 层），于是 dis[3] = 1，代表”走 1 条边”。可真实最短距离是 $2 + 1 = 3$（走上面那条路），而不是直接走下面那条长度 10 的边。BFS 数的是边数，不是长度——边权一不相等，这两件事就分家了。
更要命的是：BFS 把 3 标记完就再也不管它了。哪怕后来从 2 走过去只要 3 的代价，dis[3] 也改不回来。
问题的根源：BFS 假设”先被发现的点，距离一定更小”。边权相等时这是对的；边权不等时，一条边数少但很长的路会抢在边数多但很短的路前面被发现。
修复思路：既然队列的”先进先出”不再对应”距离从小到大”，那就换一个能真正按距离取出最小值的容器。这就是本讲的全部。
在讲任何算法之前，先把这一行认下来：
if (dis[u] + w < dis[v]) dis[v] = dis[u] + w; // 松弛 (relax) 边 u -> v
含义：我现在知道到 $u$ 的一条路长 dis[u]，$u$ 到 $v$ 有条长 $w$ 的边，那么”经过 $u$ 再到 $v$“这条路长 dis[u] + w。如果它比我已知的到 $v$ 的最短路更短，就更新。
“松弛”这个名字的来历：想象 dis[v] 是一根绷紧的橡皮筋的长度上界，每次发现更短的路就把它放松一点。它只会变小，不会变大。
本系列后面三讲的最短路算法，全部由这一行加上”以什么顺序松弛哪些边”构成：
算法 松弛顺序 Dijkstra（本讲） 每次挑当前 dis最小的未定点，松弛它的所有出边Bellman-Ford（第 06 讲） 无脑把所有边松弛 $n-1$ 轮 SPFA（第 06 讲） 只松弛” dis刚变小的点”的出边（队列优化）Floyd（第 07 讲） 按”允许用前 $k$ 个点中转”分阶段松弛 它们的区别只在顺序，不在这一行。 记住这句话，后面三讲会轻松很多。
一个立刻可用的推论：只要 dis 数组里的每个值都对应一条真实存在的路径，那么它永远是”上界”——算法结束时如果没有边可以再松弛，dis 就是答案。这条性质对上面四个算法全都成立。