一、怎么选工具
| 场景 | 算法 | 复杂度 |
|---|---|---|
| 无权图可达性 / 最少步数 | BFS | O(n + m) |
| 边权 0/1（最少修改次数等） | 0-1 BFS（双端队列） | O(n + m) |
| 非负权单源最短路 | Dijkstra（堆优化） | O(m log n) |
| 多点对最短路、n ≤ 400 | Floyd | O(n³) |
| 只问"能不能到"且 n ≤ 10⁴ | Floyd 的 bitset 版 | O(n³ / 64) |
负权边：出现负权就不能用 Dijkstra（会算错），提高级一般考 SPFA 判负环或直接避开，见到负权先警觉。
二、BFS：按层扩散的洪水
从起点出发，队列保证"先发现的点先扩展"，因此每个点第一次出队时的步数就是最少步数。应用：
- 可达性判断：如 P1514 引水入城第一问——从第一行每个蓄水池 BFS，标记能到达的沙漠城市；
- 最少操作步数：状态即节点、操作即边，BFS 第一次到达终点的层数就是答案；
- AC 自动机建 fail：fail 指向的节点一定更浅，BFS 序保证父亲先算好（见AC 自动机）。
queue<int> q; q.push(s); vis[s] = 1; dist[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) if (!vis[v]) {
vis[v] = 1; dist[v] = dist[u] + 1; q.push(v);
}
}三、Dijkstra：每次锁定最近的那个点
维护 dist[]（起点到各点的当前最短路），用小根堆每次取出 dist 最小的未确定点 u——非负权保证它的 dist 已经最优（"确定"），再用 u 松弛所有出边：
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> q;
dist[s] = 0; q.push({0, s});
while (!q.empty()) {
auto [d, u] = q.top(); q.pop();
if (d != dist[u]) continue; // 懒删除：过期堆顶直接跳过
for (auto [v, w] : g[u])
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
q.push({dist[v], v});
}
}直觉：非负权下，离你最近的那个未确定点不可能再有更近的绕法——任何绕行都要先经过更远的点。这就是 Dijkstra 的贪心正确性。
走查一遍
| 步骤 | 锁定（dist 最小的未确定点） | 松弛后 dist[2] / dist[3] / dist[4] |
|---|---|---|
| 初始 | — | ∞ / ∞ / ∞（dist[1]=0） |
| 1 | ①（0） | 2 / 5 / ∞ |
| 2 | ②（2） | 2 / 3（2+1 比 5 小）/ 8 |
| 3 | ③（3） | 2 / 3 / 6（3+3 比 8 小） |
| 4 | ④（6） | 结束：1→2=2，1→3=3，1→4=6 |
四、Floyd：三行代码的多点对最短路
for (int k = 1; k <= n; k++) // k 必须最外层：只允许经过前 k 个点
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);适用：n ≤ 400 左右、需要任意两点间最短路，或作为"建图小工具"（先 Floyd 求出关键点两两距离，再在新图上做 状压 DP——"k 个关键点 + 大图"套路的常见第一步）。三重循环顺序 k-i-j 不能换，换了对部分数据会算出非最短路。
五、易错点清单
- Dijkstra 判过期用
d != dist[u]（或 vis 数组），漏判不会错但慢，判错条件会直接出锅。 - dist 初值 INF 取
4e18级别（long long），加法前先判dist[u] != INF防溢出。 - BFS 入队时就打 vis 标记，不要等出队——否则同一节点会重复入队炸队列。
- Floyd 的 k 放最外层；f[i][i] 初始化 0，无边初始化 INF 且 INF 别参与加法。
- 重边、自环：建图时保留最小边权即可，别假设输入没有。
六、练习
- P1514 引水入城（BFS 可达性 + 区间覆盖贪心）
- P4779【模板】单源最短路径（标准版）
- 组合：Floyd 预处理关键点距离 → 状压 + MST（CSP-S 2025 道路修复套路）