首页 > 代码库 > Floyed算法c语言实现
Floyed算法c语言实现
#include<stdio.h>
#include<stdlib.h>
#define max 1000000000
int d[1000][1000],path[1000][1000];
int main()
{
int i,j,k,m,n;
int x,y,z;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
d[i][j]=max;
path[i][j]=j;
}
for(i=1;i<=m;i++) {
scanf("%d%d%d",&x,&y,&z);
d[x][y]=z;
d[y][x]=z;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) {
if(d[i][k]+d[k][j]<d[i][j]) {
d[i][j]=d[i][k]+d[k][j];
path[i][j]=path[i][k];
}
}
/* for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
if (i!=j) printf("%d->%d:%d\n",i,j,d[i][j]);*/
int f, en;
scanf("%d%d",&f,&en);
int ans = 0,p;
while (f!=en) {
printf("%d->",f);
p = path[f][en];
ans += d[f][p];
f=path[f][en];
}
printf("%d\n%d",en,ans);
return 0;
}/*
9 18
1 2 1
1 3 4
1 4 5
1 5 6
2 6 7
3 6 5
3 7 2
4 7 4
4 8 7
5 8 6
6 9 5
7 9 4
8 9 1
2 3 2
3 4 4
4 5 3
6 7 4
7 8 2
1 9*/
最短路为8
Floyed算法c语言实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。