最短路径（上）

---

一、核心概念铺垫：单源最短路径

1. 定义

从图中的**一个指定起点（源点）**出发，到图中其余所有顶点的最短路径（路径权值总和最小），称为「单源最短路径」。

• 路径权值：可以是距离、危险指数、血量损失等（对应之前题目中的公路长度、藏宝图危险指数、艾泽拉斯公路血量损失）。
• 核心目标：求「一个起点」到「所有其他点」的最优解。

2. 适用场景

• 从暴风城（1号）到奥格瑞玛（n号）的最小血量损失（Dijkstra 题目）。
• 从电车起点A到终点B的最少切换次数（0-1 BFS 题目，本质也是单源最短路径的变种）。
• 从岛屿1到岛屿n的最小危险指数（藏宝图题目，单源可扩展为多源）。

3. 关键注意点

• 路径可以是有向边（如藏宝图中岛屿航线、艾泽拉斯公路双向可视为两条有向边）或无向边（如村庄重建题目中的公路）。
• 边权可以是非负数（大部分题目场景，如 Dijkstra 适用场景）或负数（需用 Bellman-Ford 或 SPFA，本次不重点总结）。
• 不可达场景：需用「极大值（INF）」标记，最终判断结果是否≥INF，输出对应不可达标识（如 -1、AFK）。

---

二、Dijkstra（迪杰斯特拉）算法：单源最短路径的最优解（边权非负）

1. 核心思想

「贪心策略」+「松弛操作」：每次从「未确定最短路径的顶点」中，选出当前距离源点最近的顶点，以它为中间点，松弛它到所有邻接顶点的路径，逐步确定所有顶点的最短路径。

2. 核心步骤（结合之前题目实现）

1. 数据存储：用「邻接表」存储图（适配大数据量，如 n≤1e5、m≤5e5），避免邻接矩阵的内存浪费（邻接矩阵仅适配 n≤1000 的场景）。
2. 初始化：

• 距离数组 dist[]：dist[源点] = 0，其余初始化为 INF（标记不可达）。
• 优先队列（小根堆）：存储 (当前距离, 顶点编号)，初始入队 (0, 源点)，用于快速找到当前距离源点最近的顶点。

3. 核心循环（松弛操作）：

• 取出优先队列队首（距离最小的顶点 u）。
• 若该顶点的当前距离大于 dist[u]，说明是过时信息，直接跳过（避免无效操作）。
• 遍历顶点 u 的所有邻接边 (v, w)（v 是邻接顶点，w 是边权），若 dist[v] > dist[u] + w，更新 dist[v] = dist[u] + w，并将 (dist[v], v) 入队。

4. 结果输出：dist[] 数组即为源点到所有顶点的最短路径，不可达顶点的 dist[] 仍为 INF。

3. 优化点与适用场景

• 优化1：用「小根堆」替代暴力遍历找最小距离顶点，将时间复杂度从 O(n²) 优化到 O(m log n)，适配大数据量。
• 优化2：离线处理时，可添加「顶点筛选条件」（如艾泽拉斯题目中，仅允许经过 f[v] ≤ mid 的顶点）。
• 适用场景：边权非负（贪心策略的前提，若边权为负，会导致已确定最短路径的顶点被再次松弛，结果错误），单源最短路径查询（如从一个起点出发，求到其余所有点的最优解）。
• 题目对应：艾泽拉斯逃生（验证二分答案的最小血量损失）、电车最短切换次数（0-1 BFS 是其变种）、大点数单源最短路（n≤1e5）。

4. 关键细节

• 数据类型：边权较大时（如 w≤1e9），需用 long long 存储 dist[]，避免溢出。
• 输入输出：大数据量时，用 scanf/printf 或关闭 cin/cout 同步，提升速度。
• 双向边：需在邻接表中添加 u→v 和 v→u 两条边（如村庄重建、艾泽拉斯题目）。

---

三、Floyd-Warshall（弗洛德）算法：多源最短路径的简洁解

1. 核心思想

「动态规划」+「三重循环枚举中间点」：枚举所有可能的中间顶点 k，对于每一对顶点 (i, j)，判断「i→k→j」是否比「i→j」更优，若是则更新最短路径，最终得到所有顶点对之间的最短路径（多源最短路径）。

2. 核心公式

对于任意顶点 i, j, k，有：

d[i][j] = min(d[i][j], d[i][k] + d[k][j])

• d[i][j]：存储顶点 i 到顶点 j 的最短路径长度。
• 核心逻辑：通过中间点 k，间接路径可能比直接路径更优。

3. 核心步骤（结合之前题目实现）

1. 数据存储：用「邻接矩阵」存储图（d[N][N]），仅适配 n≤200（或 n≤1000）的小规模场景，优点是代码简洁，无需复杂数据结构。
2. 初始化：

• 对角线 d[i][i] = 0（自身到自身的路径长度为 0）。
• 有直接边的顶点对 (i, j)，d[i][j] = 边权（无向边需同时设置 d[j][i] = 边权）。
• 无直接边的顶点对，d[i][j] = INF（标记初始不可达）。

3. 三重循环更新（核心）：

• 外层循环：枚举中间点 k（从 0 到 n-1 或 1 到 n，对应顶点编号）。
• 中层循环：枚举起点 i。
• 内层循环：枚举终点 j。
• 执行松弛操作：d[i][j] = min(d[i][j], d[i][k] + d[k][j])。

4. 结果输出：d[N][N] 矩阵即为所有顶点对的最短路径，不可达顶点对的 d[i][j] 仍为 INF。

4. 优化点与适用场景

• 优化1：增量更新（离线场景）：如村庄重建题目，利用「村庄重建时间升序」和「询问时间不下降」的特性，无需一次性枚举所有中间点 k，而是逐步添加中间点 k（已重建的村庄），仅更新新增 k 对应的路径，提升大量询问场景的效率。
• 优化2：传递闭包（无权重场景）：如数字变换题目，将路径长度替换为「可达性标记（0/1）」，公式改为 d[i][j] = d[i][j] || (d[i][k] && d[k][j])，用于求所有顶点对的可达性。
• 适用场景：
• 多源最短路径查询（需求所有顶点对之间的最短路径，如藏宝图题目，预处理所有岛屿对的最短路径）。
• 小规模图（n≤200），三重循环 O(n³) 复杂度可接受。
• 有向图或无向图均可（无需额外修改，仅初始化邻接矩阵时区分即可）。
• 边权可正可负（但不能存在负权回路，否则最短路径不存在）。
• 题目对应：藏宝图（岛屿多源最短路径预处理）、村庄重建（增量 Floyd 处理动态询问）、数字变换（传递闭包求可达性）。

5. 关键细节

• 循环顺序：必须先枚举中间点 k，再枚举起点 i 和终点 j，否则无法正确推导间接路径（若先枚举 i 或 j，中间点 k 未被完全遍历，无法形成完整的 i→k→j 路径）。
• 极大值选择：INF 需大于最大可能的路径长度（如 n×最大边权），避免松弛操作时溢出（如 d[i][k] + d[k][j] 超过 int 范围，需用 long long）。
• 不可达判断：最终结果需判断 d[i][j] ≥ INF（而非 == INF），避免浮点误差或溢出导致的判断错误。

---

四、多源最短路径：Dijkstra 算法优化方案

1. 核心思想

多源最短路径的核心目标是「求所有顶点对之间的最短路径」，除了 Floyd 算法，还可以对「每个顶点都运行一次 Dijkstra 算法」，得到所有顶点对的最短路径，这是 Floyd 算法的补充方案，适配「大顶点数、小边数」的场景。

2. 核心步骤

1. 数据存储：用「邻接表」存储图（适配大数据量，如 n≤1e4）。
2. 循环执行 Dijkstra：对每个顶点 i（作为源点），运行一次 Dijkstra 算法，得到 i 到所有顶点的最短路径，存入 d[i][j]（j 为终点）。
3. 结果整理：d[N][N] 矩阵即为所有顶点对的最短路径，不可达顶点对的 d[i][j] 仍为 INF。

3. 优劣对比（与 Floyd 算法）

特性	Floyd 算法	Dijkstra 优化方案（多源）
时间复杂度	O(n³)	O(n × m log n)
空间复杂度	O(n²)（邻接矩阵）	O(n²)（结果矩阵）或 O(m)（邻接表）
适用顶点数	小规模（n≤200）	中大规模（n≤1e4）
边权要求	可正可负（无负权回路）	非负（贪心策略前提）
代码简洁性	高（三重循环，无需复杂数据结构）	较低（需实现 Dijkstra 封装，循环调用）
效率（大边数）	高	低（m 较大时，log n 开销明显）

4. 适用场景

• 顶点数 n 较大（如 n=1e4），边数 m 较小（如 m=5e4），Floyd 算法 O(n³) 复杂度无法承受，而 Dijkstra 优化方案 O(n × m log n) 复杂度可接受。
• 边权均为非负数（符合 Dijkstra 算法的适用条件）。
• 需预处理所有顶点对的最短路径，后续进行大量查询（如藏宝图题目，若 n 较大，可替换为 Dijkstra 优化方案）。

---

五、核心知识点总结（关键回顾）

1. 单源最短路径：从一个起点到所有其他点的最优路径，核心算法是 Dijkstra（边权非负）。
2. Dijkstra 算法：贪心+松弛，邻接表+小根堆优化，时间复杂度 O(m log n)，适配大数据量、边权非负的单源场景。
3. Floyd 算法：动态规划+三重循环，邻接矩阵存储，时间复杂度 O(n³)，代码简洁，适配小规模、多源、边权可正可负的场景，支持增量更新和传递闭包。
4. 多源最短路径优化：小规模用 Floyd，中大规模（边权非负）用「循环执行 Dijkstra」，根据数据范围选择合适方案。
5. 关键技巧：

• 二分答案+最短路验证（解决「最大最小」类问题，如艾泽拉斯逃生）。
• 离线处理+增量更新（解决动态询问问题，如村庄重建）。
• 极大值选择+数据类型防溢出（避免结果错误）。