最短路

一、基础单源最短路（无负权）

1. 题型特征（如何识别）

• 图中所有边权非负
• 问题形式通常是：
- 从起点 s 到各点的最短距离
- 或从 s 到 t 的最短路
• 图规模较大（n、m 可到 10^5 级别）



2. 解决方案





（1）Dijkstra 算法（堆优化）



• 适用条件：边权 ≥ 0
• 时间复杂度：O((n + m) log n)
• 核心思想：
- 贪心：每次确定当前距离最小的未确定点
- 利用优先队列维护最小距离



（2）实现要点



• 使用邻接表存图
• dist 数组初始化为 INF
• priority_queue（小根堆）
• 判重：弹出堆时若 d > dist[u] 则跳过

------



二、含负权边的最短路





1. 题型特征



• 明确出现负权边
• 通常会问：
- 是否存在负环
- 或在保证无负环前提下求最短路



2. 解决方案





（1）Bellman-Ford 算法



• 适用条件：允许负权
• 时间复杂度：O(nm)
• 核心思想：
- 每一轮松弛所有边
- 最多进行 n−1 轮
- 第 n 轮若还能松弛 ⇒ 存在负环



（2）实现要点



• 使用边表（edge list）
• 注意溢出（INF + w）
• 判断负环：第 n 轮是否更新

------



三、SPFA 及其判负环





1. 题型特征



• 图较稀疏
• 允许负权
• 常出现：
- 多组数据
- 在线评测（时间敏感）



2. 解决方案





（1）SPFA 算法



• 本质：Bellman-Ford 的队列优化
• 平均性能较好，最坏 O(nm)



（2）负环判定方法



• 方法一：某个点入队次数 ≥ n
• 方法二：松弛次数统计



（3）使用建议



• 数据不恶意时可用
• 竞赛中慎用（易被卡）

------



四、全源最短路问题





1. 题型特征



• 问任意两点之间最短路
• n 通常较小（n ≤ 500）
• 图较稠密



2. 解决方案





Floyd-Warshall 算法



• 时间复杂度：O(n³)
• 核心思想：
- 枚举中转点 k
- 状态转移：
- dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])



实现要点



• 初始化 dist[i][i] = 0
• 注意溢出

------



五、多源最短路





1. 题型特征



• 有多个起点
• 求任意点到最近源点的距离



2. 解决方案





虚拟源点法



• 新建超级源点 S
• 从 S 向所有源点连权值为 0 的边
• 对 S 运行 Dijkstra / SPFA

------



六、0-1 最短路（特殊权值）





1. 题型特征



• 边权只可能是 0 或 1
• 常见于：状态转换、网格图



2. 解决方案





0-1 BFS



• 使用双端队列 deque
• 权值为 0：push_front
• 权值为 1：push_back
• 时间复杂度：O(n + m)

------



七、分层图最短路（状态扩展）





1. 题型特征



• 路径中允许：
- 使用一次/多次特殊操作
- 跳过、免费、反转等
• 状态不仅与“点”有关，还与“使用次数/状态”有关



2. 解决方案





分层建图 + Dijkstra



• 将一个点拆成多个状态层
• 每一层表示一种状态
• 按规则连边



常见场景



• 免费一次
• k 次特殊技能
• 带限制的最短路

------



八、带限制条件的最短路





1. 题型特征



• 有额外约束：
- 路径长度 ≤ k
- 费用 ≤ budget



2. 解决方案





状态扩展 + 最短路



• 状态： (点, 已用资源)
• 使用 Dijkstra / BFS / DP

------



九、最短路 + 计数 / 方案数





1. 题型特征



• 除最短距离外，还要求：
- 最短路径条数
- 字典序最小方案



2. 解决方案



• Dijkstra 过程中同步维护：
- cnt[v]：最短路径数量
• 当发现更短路径：覆盖
• 当发现相同最短路径：累加

十、最短路题型快速识别表