单源最短路径（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代码简单，容易写，但可能会被题目卡数据。

总结：首选Dijkstra。具体采用哪种方法，视情况而定。