最短路问题总结

总结

四大最短路算法，分别是Dijkstra、Bellman_ford、SPFA 和 Floyd。

到底该怎么选择？

判断步骤

1. 有负边吗？

   • ❌ 没有 → 看第2步
   • ✅ 有 → Bellman-Ford/SPFA

2. 多个起点吗？

   • ✅ 是 → Floyd
   • ❌ 否 → 看第3步

3. 单起点到单终点吗？

   • ✅ 是 → Dijkstra（或BFS如果等权）
   • ❌ 否 → Dijkstra

算法选择表

场景	首选算法	记忆技巧
单源 + 正权	Dijkstra	"正数就迪杰"
单源 + 负权	SPFA	"负数就SPFA"
多源求最短路	Floyd	"多源用Floyd"
有负环检测	Bellman-Ford	"负环用贝尔曼"
有限步数限制	Bellman-Ford	"限步用贝尔曼"

特殊情况

• A* : 工程实际应用首选（游戏、导航）
• BFS : 等权图的最简单选择
• 堆优化 : 不确定就用优化版，性能更好