几种最短路算法对比

几种最短路算法对比：

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

注：$n$ 为点的个数，$m$ 为边的个数。