最短路算法

Dijkstra算法

1. 首先初始化一个距离数组为无穷
2. 迭代n次：寻找不在集合中并且dist最小的点t，并且用这个点更新其他所有点的距离，并把t加入到集合中去

因此时间复杂度为$O(n^2)$

堆优化Dijkstra算法

1. 首先初始化一个距离数组为无穷，并把定点入堆。
   堆中元素为pair<dist, #node>，因此堆一直都是按照dist排序的，从而把寻找最小dist的操作降低到$O(logn)$
2. 每次从堆头pop一个元素t，并且用这个点更新其他所有点的距离（考察他的所有邻接节点，如果可以更新则更新，如果还没有入堆则入堆），并把t加入到集合中去

因此时间复杂度为$O(mlogn)$

• 可以看出，“选取dist最小的不在集合中节点”这一步属于贪心操作，导致Dijkstra算法不能应用于含负权边的情况

• 采用邻接表后内层循环只更新了联通的节点，因此复杂度是$O(m)$；邻接矩阵实现采用INF或者-1来代表不连通，但即使采用if特判，内层循环实际上是$\Theta(n)$的。（可能堆优化版本的常数小一点？）

Bellman-Ford算法

1. 迭代n次：对每条边，根据是否走这条边更新终点的dist

因此时间复杂度为$O(nm)$

SPFA算法

1. 首先把起点加入队列
2. 队列头节点出队。对于这一节点的所有出边，如果可以走这条边更新终点的最点距离，则终点入队并且更新距离

因此时间复杂度为$O(m)$，最坏为$O(nm)$

• 注意SPFA中的st代表的是节点是否在堆中

Floyd算法

1. 三重for，外层为点A，内层为点B,C，更新$dist(B,C) = min(dist(B,C), dist(B,A) + dist(A,C))$

因此时间复杂度为$O(n^3)$

最短路算法对比