0条评论
还没有人评论过~
身为一头刚学图论的蒟蒻,瞎捣鼓了好几天,终于学会了四种最短路算法!(^-^)V
本博文代码存图除了Bellman_Ford和Floyd都是由vector存的,链表前向星党请移步/kk。
本文将会带你了解floyd!
总的来说,Floyd大约长草
Floyd是一种求全源最短路径,时间复杂度为 \(O(N^3)\) ,空间复杂度为 \(O(N^2)\) 。
一般来说Floyd用权矩阵存图。
在求单源最短路径中,无论是空间还是时间花费较大,十分不值得。可是在求任意两点的最短路中,得到了非常广泛的应用。
本质上Floyd其实是个DP,实际上ta最是暴力((*/ω\*)
Floyd的工作原理是:
第一层循环枚举中转点,第二层循环第三层循环枚举起点和重点。
状态就是边权,没啥好说的。
最短路的状态转移方程则是:
$ gra[i][j]=gra[i][k]+gra[k][j]; $
(k为中转点,i、j为起点和终点)
现在来一起看看代码吧!
#include<iostream> #include<cstring> #define INF 99999999 #define MAXN 1000 using namespace std; int gra[MAXN][MAXN];//权矩阵 int main() { for(int p=1;p<=MAXN;p++) for(int i=1;i<=MAXN;i++) if(p==i)gra[p][i]=0; else gra[p][i]=INF; int n,m,a,b; cin>>n>>m>>a>>b; for(int p=1,x,y,z;p<=m;p++) { cin>>x>>y>>z;//输入行,列,边权 gra[x][y]=z; } //下面是经典的Floyd for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(gra[i][j]>gra[i][k]+gra[k][j] ) gra[i][j]=gra[i][k]+gra[k][j]; cout<<gra[a][b]<<endl; }