一、Dijkstra
O(nlogn)
单源最短路径
这个算法加上堆优化之后还是非常推荐的
但是dijkstra有一些不足的地方
边权不能为负数
不能判断负环
二、SPFA
最大是O(mn)
单源最短路径
这个算法其实还是非常玄学的
要是运气不好的话会到达O(mn)
所以不好掌控时间复杂度
但是它也有一些得天独厚的优势
它可以有负权边
也可以判断负环
判断负环的方法:
如果一个顶点入队列的次数超过n次
说明该图中存在负环
三、Floyed
O(n^3)
多源最短路径
这个算法跑的很慢
在n不大的情况下可以用用
但是它可以算出任意两个点之间的最短路径 还是非常不错的