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$O(V^2)$可能比 SPFA 快。

注意事项

• Dijkstra：负权边会破坏贪心策略的正确性。
• SPFA：某些竞赛题目会卡 SPFA 的最坏情况（网格图），此时需改用 Dijkstra。

1. 正权图下的王者：稳定、高效、易实现。
2. 理论基础重要：是学习贪心算法和图论的基石。
3. 竞赛安全牌：避免被出题人针对 SPFA 设计的数据卡掉（网格图）。