最短路算法总结

Dijkstra-朴素 $O(n^2)$

1. 初始化距离数组, dist[1] = 0, dist[i] = inf;
2. for n次循环 每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离
3. 将不在S中dist_min的点->t
4. t->S加入最短路集合
5. 用t更新到其他点的距离

Dijkstra-堆优化 $O(mlogm)$

1. 利用邻接表，优先队列
2. 在priority_queue<PII, vector<PII>, greater<PII>> heap;中将返回堆顶
3. 利用堆顶来更新其他点，并加入堆中类似宽搜

Bellman_ford $O(nm)$

1. 注意连锁想象需要备份, struct Edge{int a, b, c} e[M];
2. 初始化dist, 松弛dist[x.b] = min(dist[x.b], backup[x.a] + x.w);
3. 松弛k次，每次访问m条边

Spfa $O(n)$ ~ $O(nm)$

1. 利用队列优化仅加入修改过的地方
2. for k次
3. for 所有边利用宽搜模型去优化bellman_ford算法
4. 更新队列中当前点的所有出边

Floyd $O(n^3)$

1. 初始化d
2. k, i, j 去更新d