三种单源最短路径方法对比
单源最短路径
算法比较
选型指导
负权边与负环
Dijkstra、Bellman-Ford、SPFA 对比
这三个算法都能求“从一个源点出发到其他所有点的最短路”，但它们对边权条件、运行速度、稳定性和使用场景的要求并不一样。
Dijkstra
没有负权边时，通常优先选它。速度快，最稳定，竞赛和工程里最常用。
Bellman-Ford
可以处理负权边，还能判断负环，但时间复杂度偏高，适合做保底方案。
SPFA
是 Bellman-Ford 的队列优化版。某些数据很快，但最坏情况仍可能很慢，稳定性不足。
一眼先看结论
图中边权都不为负
优先选 Dijkstra。
原因：速度快，复杂度常写作 O((V + E) log V)，表现稳定。
图中可能有负权边
选 Bellman-Ford 或 SPFA。
如果要求稳并且要判断负环，Bellman-Ford 更直接。
题目还要求判断负环
Bellman-Ford 最标准，SPFA 也常用于判负环。
但课堂上讲原理时，Bellman-Ford 更清晰。
| 比较项目 | Dijkstra | Bellman-Ford | SPFA |
|---|---|---|---|
| 核心思想 | 每次确定一个当前最近且未确定的点，再向外更新 | 反复对所有边做松弛，最多做 V-1 轮 | 把“可能还能继续更新别人的点”放进队列，只处理这些活跃点 |
| 能否处理负权边 | 不可以 | 可以 | 可以 |
| 能否判断负环 | 不适合 | 可以，额外再检查一轮松弛 | 可以，常用“入队次数是否超过 V”判断 |
| 常见复杂度 | O((V + E) log V) | O(VE) | 平均常较快，最坏仍可能到 O(VE) |
| 稳定性 | 最稳定 | 稳定，但偏慢 | 不稳定，容易被卡 |
| 适合稠密图 / 稀疏图 | 特别适合稀疏图配合邻接表和优先队列 | 都能做，但边多时会更慢 | 一般也用于邻接表，但性能受数据影响大 |
| 课堂理解难度 | 中等，需要理解贪心正确性 | 最直观，适合讲“松弛”概念 | 写法不难，但性能分析最容易讲不清 |
| 比赛中常见选择 | 无负边时首选 | 有负边时的标准方案 | 有时会用，但很多场合会谨慎避开 |
三个算法分别怎么理解
Bellman-Ford
- 源点到某点的最短路，最多只会经过 V-1 条边。
- 所以把所有边反复拿来“试着更新一下”，做够 V-1 轮就行。
- 如果第 V 轮还能更新，说明存在负环。
Dijkstra
- 每次从还没确定的点中，选当前距离最小的点。
- 一旦这个点被选中，它的最短距离就确定了。
- 这个结论依赖“边权不能是负数”，否则贪心会失效。
SPFA
- 它仍然是在做松弛，只是不再傻乎乎每轮扫所有边。
- 谁刚被更新，就让谁进队列，表示“它可能还能影响别人”。
- 有时很快，但在构造数据下可能退化，不能盲目当作“永远更优”。
共同点
- 三者本质上都围绕“松弛操作”展开。
- 松弛的意思是：如果经过一条边可以让答案更短，就更新答案。
- 区别主要在于：按什么顺序松弛、松弛多少次、哪些点需要被处理。
为什么 Dijkstra 不能处理负权边
因为 Dijkstra 的核心假设是：当前最小的那个未确定点，已经不可能再被后面的路径变得更小。
如果存在负权边，这个假设就可能被打破。也就是说，某个点刚被“确定”，后面却又通过一条负边找到了更短的路径，这样贪心结论就错了。
什么时候不太建议用 SPFA
- 当题目数据范围大，而且出题人可能专门卡算法时。
- 当你只需要处理非负权图时，因为这时 Dijkstra 更稳更快。
- 当课堂目标是讲清楚原理时，因为 SPFA 的“为什么有时快、有时慢”不如另外两种直观。