---恢复内容开始---
Floyed算法模板题
Floyed算法
1.计算图中任意两点间的最短路径
2.适用于出现负边权
3.算法描述：
（1）初始化：点u,v如果有边相连，则dis[u][v]=w[u][v]
如果不相连，则dis[u][v]=0x7fffffff
（2） for ( int k=1 ; k<=n ; k++ ) //k为中间点
for ( int i=1 ; i<=n ; i++ )
for ( int j=1 ; j<=n ; j++ )
if (f [ i ] [ j ] > f [ i ] [ k ] + f [ k ] [ j ] )
f [ i ] [ j ] = f [ i ] [ k ] + f [ k ] [ j ] ;
（3）算法结束：dis[i][j]得出的就是从 i 到 j 的最短路径
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> using namespace std; int n,m,s,t,x,y; int a[101][3]; double f[101][101]; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i][1]>>a[i][2]; cin>>m;
memset(f,0x7f,sizeof(f)); //先初始化为一个较大内容的数组 for(int i=1;i<=m;i++) { cin>>x>>y; f[x][y]=f[y][x]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2)); } cin>>s>>t;
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&i!=k&&j!=k&&f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j];
printf("%.2lf",f[s][t]); return 0; }
---恢复内容结束---
原文：https://www.cnblogs.com/xiaoyezi-wink/p/10745308.html