系列文章目录
单源最短路径（1）：Dijkstra算法 单源最短路径（2）：Bellman_Ford算法 单源最短路径（3）：SPFA算法 单源最短路径（4）：总结
在早些时候学习最短路径算法时，心里就一直有个疑问，如果一个图仅仅是存在负权，但不构成负权回路，又该如何？我们一个一个看。
Dijkstra算法，
观察上图，若A作为源点，在第一轮循环后，B被标记数组标记，但我们发现在第二轮循环中，B还可以通过C点继续进行更新。由此，可以得出结论：Dijkstra算法不适用于负权图。
Bellman_Ford算法和SPFA算法，
我们先思考下上述“因B点被标记数组标记而导致无法通过C点再更新”的问题，归根结底是标记数组的锅。有人提议，不妨去掉标记数组，如果去掉，就会造成很严重的问题，首当其冲的是“无法求出dist[]的最小值”。
反观Bellman_Ford算法和SPFA算法，它们不存在标记数组的问题，因此对于仅仅存在负权的图，它们都可以工作的很好。
最后，读者需要注意的是，如果是无向图，只要存在一条负边，该图就存在负权回路，这不难理解，无向图的一条边相当于有向图的往返两条边。
| 算法 | 时间复杂度 | 原理 |
|---|---|---|
| Dijkstra | 贪心 | |
| Bellman_Ford | 动态规划 | |
| SPFA | 贪心 |
Bellman_Ford没什么好说的，能不用就不用。
国际上一般不承认SPFA算法，首先在SPFA算法论文中，对它的复杂度证明存在错误，其次Bellman_Ford的论文中早已提及这个队列优化，所以SPFA并不算是新创的优化算法。
另外，SPFA算法有两个优化策略：SLF和LLL。
- SLF，Small Label First 策略，设要加入的节点是j，队首元素为i，若
dist[j] < dist[i]，则将j插入队首，否则插入队尾； - LLL，Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若
dist[i] > x则将i插入到队尾，查找下一元素，直到找到某一i使得dist[i] <= x，则将i出队进行松弛操作。
SLF 可使速度提高 15 ~ 20%，SLF + LLL 可提高约 50%。 但这两个优化本身是需要额外的复杂度的，甚至可能需要重新设计一套数据结构，来高效完成队首与队尾的插入。
因此，个人建议，在实际的应用中尽量不要采用SPFA算法。其时间效率也不是很稳定，为了避免最坏情况的出现，还是应该使用效率更加稳定的Dijkstra算法。
使用邻接表+二叉堆优化的Dijkstra算法，复杂度适宜，也稳定，就是有个缺陷，不能处理负权回路。
最后，我发现在算法竞赛中我们大多数的选择还是SPFA，知乎了下，邻接表+二叉堆优化的Dijkstra写起来复杂，容易错，而SPFA代码简单，容易写，但可能会被题目卡数据。国内的赛事应该不会出现卡数据的现象，国际赛事就不一定了，鉴于我在这方面不是很了解，所以就不多说了。但还是友情提醒下各位ACMer，若某题使用SPFA被判定为超时，您应该考虑下该题的SPFA是否被卡数据了。
**总结：首选Dijkstra。**具体采用哪种方法，视情况而定。