最短路

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

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]：最短路径数量
• 当发现更短路径：覆盖
• 当发现相同最短路径：累加

---

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

题面特征	首选算法
无负权	Dijkstra
有负权	Bellman-Ford / SPFA
权值仅 0/1	0-1 BFS
任意两点	Floyd
多起点	虚拟源点
状态限制	分层图

【前置知识点】
1、广度优先搜索

【后置知识点】
1、并查集

【思维导图】

【题目知识点分类】