入门：单源 vs 全源、松弛操作与四算法适用场景
基于通用算法概念 · 核于 2026-07
速查
- 定义：最短路径是在带权图里求从一个顶点到另一顶点（或所有顶点）的权和最小的路径；权通常表示距离、耗时、费用等代价。
- 两大问题形态：单源最短路（SSSP）——求某源点
s到其他所有点的最短路；全源最短路（APSP）——求任意两点间的最短路。 - 权的关键分野：非负权（所有边权 ≥ 0）→ 可用 Dijkstra；可负权（允许负边）→ 必须用 Bellman-Ford/SPFA；若有可达的负权环则最短路无定义（可无限绕圈变小）。
- 松弛操作（relax）：所有最短路算法的核心——
if (d[u]+w(u,v) < d[v]) d[v] = d[u]+w，即「发现更短的路径就更新」；四种算法本质是松弛策略与执行次数的差异。 - Dijkstra：贪心 + 小顶堆，每轮取出
d[]最小的未确定顶点，松弛其邻居，要求非负权，复杂度 O((V+E)log V)，适合大多数非负权单源场景。 - Bellman-Ford：暴力松弛所有边 V−1 轮，可处理负权，第 V 轮仍能松弛则存在负权环，复杂度 O(VE)——朴素但能判负环。
- SPFA（Shortest Path Faster Algorithm）：Bellman-Ford 的队列优化——只把「刚被松弛、
d[]变小的点」入队再松弛其邻居，平均 O(E) 但最坏仍 O(VE)，易被构造数据卡。 - Floyd-Warshall：全源最短路，三重循环 DP，
dp[k][i][j]=min(dp[k-1][i][j], dp[k-1][i][k]+dp[k-1][k][j])，复杂度 O(V³)，适合稠密小图、求传递闭包。 - 判负环：只有 Bellman-Ford/SPFA 能判负环（Dijkstra 不能处理负权）；BF 看第 V 轮是否仍能松弛，SPFA 看某点入队次数是否 ≥ V。
- 选型口诀：非负权单源 → Dijkstra；负权或要判负环 → Bellman-Ford/SPFA；全源或小图稠密图 → Floyd。
- 邻接表 vs 邻接矩阵：稀疏图（E≪V²）用邻接表配 Dijkstra/BF；稠密图或 V 很小用邻接矩阵配 Floyd——存储结构要与算法匹配。
- 升级路径：Dijkstra（单源非负权）→ Bellman-Ford（单源负权）→ Floyd（全源）→ A*（带启发式的单点对最短路，见搜索叶）。
- 交互演示：Dijkstra 可视化 · Bellman-Ford 可视化 · Floyd-Warshall 可视化。
一、两大问题形态：单源 vs 全源
最短路径问题按「求几个点对」分为两类，对应不同算法阵营：
| 形态 | 问题 | 一次求出 | 典型算法 |
|---|---|---|---|
| 单源最短路（SSSP） | 源点 s 到其他所有点的最短路 | V−1 条路径 | Dijkstra / Bellman-Ford / SPFA |
| 全源最短路（APSP） | 任意两点间的最短路 | V×(V−1) 条路径 | Floyd-Warshall |
- 单源：只要一个起点。GPS 导航「从当前位置到所有目的地」、网络路由「本节点到全网」都是单源。注意：单源算法跑 V 次（每个点当一次源）也能得到全源，但稀疏图下 V 次 Dijkstra 是 O(V(V+E)logV)，通常比 Floyd 的 O(V³) 好。
- 全源：要所有点对。典型如「任意两个城市的距离表」「图的可达性（传递闭包）」。Floyd 一次三重循环搞定，但只适合 V 较小（≤几百）的图——V=1000 时 Floyd 是 10⁹ 次运算，已经吃力。
为什么不全用「跑 V 次单源」代替 Floyd
- 稠密图（E≈V²）：V 次 Dijkstra 是 O(V·(V²)logV) = O(V³logV)，比 Floyd 的 O(V³) 还慢——此时 Floyd 更优。
- 稀疏图（E≈V）：V 次 Dijkstra 是 O(V·(V)logV) = O(V²logV)，比 Floyd 的 O(V³) 快得多——此时「跑 V 次 Dijkstra」更优。
- 所以选型看图密度：稠密小图选 Floyd，稀疏大图选「V 次 Dijkstra」。
二、权的关键分野：非负权 vs 可负权
边权的正负直接决定算法选型，是最容易踩坑的维度：
- 非负权（所有边权 ≥ 0）：首选 Dijkstra。贪心策略成立的前提就是「边权非负」——已确定的最短路不会被后来的负边推翻。
- 可负权（允许负边）：必须用 Bellman-Ford / SPFA。Dijkstra 的贪心假设在负权下被破坏，会算出错误答案。典型场景：带「收益」（负权表示获利）的最短路、汇率套利（负环表示无限套利）。
- 负权环：若从源点可达一个权值和为负的环，则绕这个环无限次可让路径长度趋于 −∞，最短路无定义。此时算法应能检测并报告负环（Bellman-Ford 第 V 轮、SPFA 入队次数 ≥ V）。
Dijkstra 遇负权为什么算错
Dijkstra 一旦把某顶点 u 标记为「已确定」（d[u] 最小且出堆），就再也不更新它。但若有负边，后面可能发现一条「经负边到 u 更短」的路径，Dijkstra 已经锁死 d[u] 不再更新，导致错误。详见Dijkstra 与 Bellman-Ford。
三、松弛操作：所有算法的共同内核
四种最短路算法千差万别，但内核只有一个操作——松弛（relax）：
// 松弛边 (u, v, w)：尝试用「经 u 到 v」的路径更新 d[v]
function relax(u, v, w):
if d[u] + w < d[v]:
d[v] = d[u] + w // 发现更短路径，更新
prev[v] = u // 记录前驱（用于还原路径）- 直觉：
d[v]维护「目前已知的s到v最短距离」，每次发现更短的就更新。初始d[s]=0，其余d[]=+∞。 - 正确性根基：最短路径的子路径也是最短路径（最优子结构）——若
s→v的最短路经过u，则s→u这段也必是s→u的最短路。所以只要把所有「能松弛」的边松弛够，d[]最终收敛到真实最短路。 - 四种算法的差异在于「松弛哪些边、松弛几轮、按什么顺序松弛」：
| 算法 | 松弛策略 | 松弛次数 | 何时停 |
|---|---|---|---|
| Dijkstra | 每轮取 d[] 最小的未确定点，松弛其出边 | 每条边松弛一次（贪心确定） | 所有点确定 |
| Bellman-Ford | 暴力松弛所有边，重复 V−1 轮 | V−1 轮 × E 条边 = O(VE) | V−1 轮后必收敛 |
| SPFA | 只松弛「刚被更新点的出边」（队列） | 平均每边松弛常数次 | 队列空 |
| Floyd | DP：依次以每个点 k 为中转松弛所有点对 | V 轮 × V² 对 = O(V³) | 中转点遍历完 |
四、四算法适用场景速览
| 算法 | 问题 | 权限制 | 复杂度 | 适用场景 | 判负环 |
|---|---|---|---|---|---|
| Dijkstra（堆优化） | 单源 | 非负权 | O((V+E)logV) | 非负权单源主力（导航、路由） | ❌ |
| Bellman-Ford | 单源 | 可负权 | O(VE) | 负权图、要判负环 | ✅（第 V 轮） |
| SPFA | 单源 | 可负权 | 平均 O(E)，最坏 O(VE) | BF 的工程优化，竞赛慎用（易被卡） | ✅（入队 ≥ V） |
| Floyd-Warshall | 全源 | 可负权（无负环） | O(V³) | 全源、稠密小图、传递闭包 | ❌ |
一句话选型
- 非负权 + 单源 → Dijkstra（最常见，GPS/路由默认）
- 有负权 / 要判负环 → Bellman-Ford（稳妥）或 SPFA（平均快但易被卡）
- 全源 / V 很小（≤500）/ 要求传递闭包 → Floyd
- 稀疏大图要全源 → 跑 V 次 Dijkstra（比 Floyd 快）
五、典型应用场景
- 地图导航：道路网（边权=距离/耗时，非负）求最短路线 → Dijkstra（A* 是带启发式的升级，见搜索叶）。
- 网络路由：OSPF 协议用 Dijkstra 算「本路由器到全网」的最短路，更新路由表。
- 汇率套利：把汇率取负对数当边权，负权环意味着无限套利机会 → Bellman-Ford 判负环。
- 依赖分析 / 可达性：求「A 能否到达 B」的传递闭包 → Floyd（或 DFS/BFS，Floyd 适合稠密图多次查询）。
- 任务调度：带约束的最长路（关键路径）可转化为最短路（边权取负）或用拓扑排序 + DP。
下一步
理解了松弛操作和四算法的适用场景后，下一步深入单源两大利器——Dijkstra 的贪心 + 堆优化与Bellman-Ford 的 V−1 轮松弛 + 判负环，以及 Dijkstra 为何不能处理负权，见Dijkstra 与 Bellman-Ford。