参考文献： 最短路笔记

最短路中各个算法的原理

①dijkstra

时间复杂度$O(n^2)$
dijkstra是根据每次找出距离起点最近的一个点，然后用着一个点来更新其他距离，每个点只会被更新一次，用st[]进行判重

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

②dijkstra堆优化

时间复杂度$O(mlogn)$
堆优化的dijkstra就是用c++自带的priority_queue优先队列对每个点i以及起点到i的距离dist进行储存，并按照距离dist进行排序

priority_queue定义: priority_queue<PII, vector<PII>, greater<PII>> heap;

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

③bellman_ford

时间复杂度$O(nm)$

通过循环点的个数n，边的个数m，来更新所有点到起点的距离
两重循环 for n
            for 所有边 a, b, w
                dist[b] = min(dist[b], dist[a] + w)

bellman_ford可以用于求有边数限制的最短路
AcWing 853.有边数限制的最短路

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

④spfa

时间复杂度平均$O(km)$线性，最坏情况下$O(nm)$

spfa就是对bellman_ford做了一个优化
因为dist[b] = min(dist[b], dist[a] + w)
a -> b
如果dist[b]要变小，那么只有dist[a]变小了才会变小。
那么做法就是：
1.维护一个队列，先把起点放进去。
2.遍历队列，每次出队的时候标记当前的点是已经被遍历过的
3.用当前的点更新其他点的距离，更新完毕后，判断当点的是否被标记过，如果没有标记过，将这个的点放入队列中，因为此时当前点一定是距离起点最小的点，满足spfa优化条件
4.遍历完所有点后判断dist[end] > INF?  因为spfa可以用来求负权边的最短路

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

⑤floyd

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

for(int k = 1; k <= n; k ++ )   //  将其分为[i, k]和[k, j]两段，基于动态规划
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

注意事项

稀疏图和稠密图

                 稠密图          稀疏图
边与点的个数      m≈n²           m≈n
存储方式         邻接表          邻接矩阵