05 最短路：FLOYD 与 DIJKSTRA
一、本阶段目标
学完本阶段，学生要能做到：
二、最短路问题分类
类型 含义 常用算法 无权单源最短路 每条边代价都是 1，从一个起点出发 BFS 带权单源最短路 边权非负，从一个起点出发 Dijkstra 多源最短路 任意两点之间最短路 Floyd 边权有负数 可能需要 Bellman-Ford / SPFA 了解即可
深圳自招主线只需要熟练：
三、FLOYD 算法
Floyd 用来求任意两点之间的最短距离。
适合：
核心思想：
转移方程：
四、FLOYD 模板
五、FLOYD 的复杂度
适合大致范围：
六、DIJKSTRA 算法
Dijkstra 用来求：
前提：
核心思想：
七、DIJKSTRA 的直觉解释
假设你从学校出发，到所有地点都想求最短时间。
当前已知有几个候选地点距离学校最近。由于所有道路时间都是非负的：
所以可以把它的最短路“确定”下来。
这也是为什么 Dijkstra 不能处理负边权：
八、堆优化 DIJKSTRA 模板
九、DIJKSTRA 的复杂度
使用优先队列：
适合：
十、FLOYD 和 DIJKSTRA 怎么选
情况 选择 边权全是 1 BFS 点数小，问任意两点 Floyd 点数大，从一个起点出发 Dijkstra 多次单源查询 多次 Dijkstra 或 Floyd，视 n、m 而定 有负边 不用 Dijkstra，另学 Bellman-Ford/SPFA
十一、常见建模关键词
题面关键词 图论模型 最短时间 最短路 最小费用 最短路 最小消耗 最短路 最大成功率 可转化为最短路或优先队列贪心 最少换乘 BFS 或最短路 路径风险最小 最短路，或最小化最大边权
十二、最小化最大边权模型
有些题不是求路径边权和最小，而是要求路径上最大边权尽量小。
例如：
转移可以写成：
这仍然可以用 Dijkstra 思想，因为状态值也满足“越小越优”。
洛谷 P1396 营救就是类似模型。
十三、FLOYD 常见错误
错误 后果 修正 没有初始化 d[i][i]=0 自己到自己距离错误 初始化对角线为 0 INF 太小 加法溢出或错误更新 用足够大的 INF 忘记处理重边 答案偏大 min(d[u][v], w) k 循环顺序错 Floyd 语义被破坏 必须 k 在最外层
十四、DIJKSTRA 常见错误
错误 后果 修正 用于负权图 答案错误 确认边权非负 int 溢出 路径和错误 dist 用 long long 忘记 vis 或旧状态判断 重复处理多 可用 vis 或 if (d != dist[u]) continue 无向图只加一条边 路径缺失 双向加边 多组数据不清空 数据污染 清空 g、vis、dist
十五、练习题
题号 题名 训练点 建议 P3371 单源最短路径（弱化版） Dijkstra 基础 必做 P4779 单源最短路径（标准版） 堆优化 Dijkstra 必做 P1119 灾后重建 Floyd + 时间限制 必做 P1359 租用游艇 Floyd 入门 必做 P1144 最短路计数 最短路 + 计数 提高 P1396 营救 最小化最大边权 提高 P1576 最小花费 最短路建模 提高 P1629 邮递员送信 正反图 Dijkstra 提高
链接：
十六、本阶段作业
1. 写出 Floyd 的三重循环，并解释 k 为什么在最外层。
2. 写出 Dijkstra 模板，并说明优先队列里存什么。
3. 完成 P3371、P4779。
4. 完成 P1119，理解“随着时间开放节点”的变式。
5. 选做 P1396，体会最短路不一定是“求和最小”。
十七、本阶段小结
选择最短路算法时，先问：
对应关系：
