最短路问题的各种算法总结

ʕ•ﻌ•ʔ · 2021-06-03 16:21:20 · 个人记录

一、

Floyd算法：

适用范围：任意两点间的最短路

时间复杂度：O (N^3) \ \ \ \ \ \ \ 邻接矩阵存储，适合n小于300

特点：允许负权，不允许负权回路（此时显然没有最小回路，越跑越小）

变形及应用：传递闭包+最短路径条数+最小环+最大边最小+最小边最大

核心:三角松弛技术（若有更优的则更新）

for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

初始化：

    memset(d,0x3f,sizeof(d));
    d[i][i]=0
    d[i][j]=a[i][j]

重点：K层必须放在外部，k一定是由k-1更新而来。k是决定i到j的最短路径由k更新，故对于每一个k都必须从新跑所有的i和j

实际上原本公式是三维的，常见的是优化后的

原本的转移方程：d_{k,i,j} : 表示“经过若干个编号不超过k的节点”从i到j的最短距离。

d_{k,i,j}=min(d_{k-1,i,j},d_{k-1,i,k}+d_{k-1,k,j}) \ \ \ \ k>=1

应用：

①最大边最小+最小边最大

d[i][j]=min(d[i][j],max(d[i][k],d[k][j])) //最大边最小
d[i][j]=max(d[i][j],min(d[i][k],d[k][j])) //最小边最大

②传递闭包问题：

定义：若干个元素以及二元关系，并且关系具有传递性。通过传递性能推导出尽量多的元素直接的关系，这类问题称为传递闭包。

初始状态：

$i$和$j$没关系：$\ \ \ \ \ \ $ $d_{i,j}$=0 ```cpp for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=a[i][j]||(a[i][k]&&a[k][j]); //一真全真 ``` --- ③最短路径条数 ```cpp if(d[u]+a[u][v]<d[v]){ d[v]=d[u]+a[u][v]; cnt[v]=cnt[u]; //如果有更优的路线，则路径条数显然更新为“新的最短路的路径条数 } else if(d[u]+a[u][v]==d[v]) cnt[v]+=cnt[u]; //加法原理 ``` --- ⑤最小环【1】有向图：只要跑一遍Floyd 枚举每一条边即可 ```cpp ans=min{d[i][j]+a[j][i]} ``` 【2】无向图：最小三个点在floyed的第k层开始前,$d_{i,j}$是保存的是“经过编号不超过k-1” 的i到j最短路径长度。即还没有经过k点。所以： $min(d_{i,j}+a_{j,k}+a_{k,i})

1<=i<j<k

特别注意：

①注意循环的边界执行第k层时实际存下的是k-1层的东西故第一个ij循环必须要i,j<k

②j从i+1开始，保证往后找环，不会重复，因为是无向图如果找过1，2就没有必要再找2，1了

③注意顺序，一定是先更新最小环再更新最短路（因为更新最短路更新的是第k层，而更新最小环用到的是k-1层，不超过k-1层的最短路是已经求好了的，可以直接用）

④因为权值和有可能比较大，会爆int，所以需要用long long。但要注意不可以直接开long long类型，否则一开始赋初始值不好操作，三个long long 加起来可能爆。不如直接加一步强制转换，把一个int变成long long，后面就不可能爆了。

二、

Dijkstra算法

时间复杂度：O(N^2) 或O((n+m)\times log N) d_i表示起点到i的最短距离

特点：单源最短路径问题--->给定起点 n<=3000

特点：不允许存在负权

核心原理：贪心

每次找到相连的边权最小的点，加入队列，等待用这个点去松弛别的点（前提没有负边）

优先队列优化：

三、Bellman-Ford算法

时间复杂度：O(N^2)

没什么优秀的特质，不如SPFA

四、SPFA算法

特点：单源最短路+可以判负环+复杂度一般情况下不错

期望的时间复杂度：O(km) (k<2,m是边数)

实际情况下有时会被卡成O(N^2)

本质：Bellman_ford的优化

思想：只有被松弛过的点才有可能松弛其他点（否则既然当前都不是最优那用这个点去松弛别人就没意义了）

判负环：如果入队次数>n 注意不是松弛次数一个点多次被松弛不一定就有负环可能是重边

双端队列优化：SLF