首页 > 代码库 > floyd

floyd

2024-08-13 03:27:21   218人阅读

求任意两点之间的最短路径。e[i][j]为记录从i到j之间的距离，当循环结束后最后存储的就是i到j之间的最短路径啦。

floyd算法就是对于给定的n个结点，对于每一个e[i][j]，都让它经过1，然后比较e[i][j]和e[i][1]+e[1][j]的大小，来更新e[i][j]，再用2依次比较一下，同理，一直到n个结点都比较一次，所以就成了3层循环。但是我们要注意一下，floyd算法不适合带有负权值的问题，因为当存在负权值的时候就会一直循环下去，找不到最小值。而且效率有些低。。。。

技术分享
 1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<string.h> 5 using namespace std; 6 const int inf=0x3f3f3f; 7 int e[1004][1004]; 8 int main(){ 9 int m,n;10 while(cin>>n>>m){11         for(int i=1;i<=n;i++){12             for(int j=1;j<=n;j++){13                 if(i==j)e[i][j]=0;14                     else15                 e[i][j]=inf;16             }17         }18         int t1,t2,t3;19     for(int i=1;i<=m;i++){20         cin>>t1>>t2>>t3;21         e[t1][t2]=t3;22     }23     for(int k=1;k<=n;k++)///要经过的结点24     for(int i=1;i<=n;i++)25         for(int j=1;j<=n;j++)26             if(e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j];///更新结点27 for(int i=1;i<=n;i++){28     for(int j=1;j<=n;j++){29     printf("%10d",e[i][j]);30     }31     cout<<endl;}32 }33 }
View Code

 

floyd


联系
我们