Dijkstra和SPFA的区别
Fluffy_fluffy · · 算法·理论
1. 适用范围
- Dijkstra：
- 仅适用于边权非负的图（正权图）。
- 无法处理负权边或负权环。
- SPFA：
- 可以处理带负权边的图。
- 能检测负权环（如果存在则无解）。
2. 时间复杂度
- Dijkstra：
- 朴素实现：
O(V^2) （适合稠密图）。 - 优先队列优化：
O(E \log V) （适合稀疏图）。
- 朴素实现：
- SPFA：
- 平均：
O(E) - 最坏：
O(VE) 。
- 平均：
3. 实现方式
- Dijkstra：
- 维护一个优先队列，每次取当前距离最小的节点
- 节点一旦被处理，其最短路径不再更新。
- SPFA：
- 使用普通队列，动态松弛边。
- 节点可能多次入队（如果距离被更新）。
4. 负权环处理
- Dijkstra：无法检测负权环（会陷入死循环或错误）。
- SPFA：可以通过节点入队次数检测负权环（若某节点入队次数
\ge V 次，则存在负权环）。
核心区别总结
| 场景 | 算法选择 | 理由 |
|---|---|---|
| 正权图 | Dijkstra | 时间复杂度优，稳定性高，代码简单。 |
| 负权图/需检测负权环 | SPFA | Dijkstra 无法处理负权。 |
| 稀疏图 + 正权 | Dijkstra（优先队列） | |
| 稠密图 + 正权 | Dijkstra（朴素） | |
| 不确定是否有负权 | 先试 Dijkstra | 若失败再转 SPFA，避免盲目使用 SPFA 被卡。 |
如何选择？
- 正权图：优先用 Dijkstra（更稳定高效）。
- 负权图/需检测负权环：只能用 SPFA。
- 稀疏图：两者均可，Dijkstra 的优先队列优化更优。
- 稠密图：朴素 Dijkstra
O(V^2) 可能比 SPFA 快。
注意事项
- Dijkstra：负权边会破坏贪心策略的正确性。
- SPFA：某些竞赛题目会卡 SPFA 的最坏情况（网格图），此时需改用 Dijkstra。
附：
Dijkstra 不可替代的原因
- 正权图下的王者：稳定、高效、易实现。
- 理论基础重要：是学习贪心算法和图论的基石。
- 竞赛安全牌：避免被出题人针对 SPFA 设计的数据卡掉（网格图）。