几种最短路算法对比

众所周知，关于 SPFA，它死了。

几种最短路算法对比：

名称	时间复杂度	优点	缺点	使用情况
Floyd-Warshall		仅有的多源最短路径算法（即跑一遍 Floyd 能求出每个点到其它点的距离）、其核心代码就 5 行	时间复杂度过高	多源最短路、对时间复杂度没要求
Dijkstra（朴素）		无	编码复杂度非常高、不能处理负权，即边的权值是负数的情况（跟它用的是贪心有关）	不怎么用
Dijkstra（优先队列优化）		最快了	同朴素版	对时间复杂度有要求
Bellman-Ford		我个人比较喜欢的算法，能处理负权，时间复杂度还行，而且核心代码只有 4 行	跟 Dijkstra 时间复杂度互有胜负，有时还是 Dijkstra 赢了	稀疏图
SPFA	最坏也是	优化版 Bellman-Ford	众所周知，它死了	稀疏图
Jonson		仅有的全源最短路算法，结合了 Dijksra 和 SPFA 的优势	感觉跑多遍单源叫多源比较牵强、编码复杂度极高	不怎么常用……
BFS		思路简单	只能处理等权图或无权图	等权图 / 无权图

注： 为点的个数， 为边的个数。