floyd算法c
#include<stdio.h>
#defineMAXNODE108
intpath[MAXNODE+1][MAXNODE+1]={0};
intmain(void)
{
FILE*fpr,*fpw;
intva,vb,i,j,k;
fpr=fopen("in.txt","r");/*读取的文件名称in.txt*/
fpw=fopen("out.txt","w");/*path的数据在out.txt中展现*/
while(fscanf(fpr,"%d%d",&va,&vb)!=EOF)
path[va][vb]=path[vb][va]=1;
for(k=1;k<=MAXNODE;++k){
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(!path[i][k]||!path[k][j])
continue;
if(!path[i][j])
path[i][j]=path[i][k]+path[k][j];
elseif(path[i][j]>path[i][k]+path[k][j])
path[i][j]=path[i][k]+path[k][j];
}
}
}
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(i==j)
fprintf(fpw,"%-10d",0);
elseif(path[i][j])
fprintf(fpw,"%-10d",path[i][j]);
else
fprintf(fpw,"%-10d",-1);
}
fprintf(fpw," ");
}
return0;
}
注意：floyd算法中k为最外层，这是动态规划的思想，不能改变i,j,k的顺序！！！
这是之前的答案的错误之处。
-1表示不通。
具体程序分析，我可以加你QQ，愿意的话，你把QQ写给我。
② 数据结构C语言版Floyd算法
您的理解不太对啊，每个矩阵D中记录的都是顶点i到顶点j的当前所经顶点状态下的最短路径
③ C语言编程floyd法求助
for(i=0;i<n;i++){//输出每对顶点间最短路径长度及最短路径
for(j=0;j<n;j++){
printf("%d到%d的最短长度:",i+1,j+1);
printf("%d\t",D[i][j]);//输出Vi到Vj的最短路径长度
printf("\n");
}
}
修改这里的就好了。不要全部输出。
你可以定义一个变量 来累加 D[I][J]初步想法
int minzise = 0;
for(i=0;i<n;i++){//输出每对顶点间最短路径长度及最短路径
for(j=0;j<n;j++){
minzise+= D[i][j];//
}
}
printf(“%d”),minzise)//符合你要求吗？
④ floyd算法 最短路径 C语言
void Floyd(int **arr,int Vertex)
{
int i,j,k;
for(k=0;k<Vertex;k++)
for(i=0;i<Vertex;i++)
for(j=0;j<Vertex;j++)
{
if (arr[i][j]>arr[i][k]+arr[k][j])
{
arr[i][j] = arr[i][k]+arr[k][j];
}
}
}
⑤ floyd算法中输出最短路径序列的C语言代码
floyd是动态规划的简化,所以输出路径一样套用dp的典型记录方式即可.
即,每次松弛时,记录是松弛了哪一个点.然后输出时递归输出即可.
弄一个矩阵R[][]初始化为0,然后比如你的距离矩阵是D[][]
松弛改为是:
if(D[i][j] > D[i][k]+D[k][j]){
D[i][j] = D[i][k]+D[k][j];
R[i][j] = k;
}
输出时可以写一个递归函数
function out(a,b){
if(R[a][b] == 0){
return;
}
out(a,R[a][b]);
//输出k
out(R[a][b],b);
}
⑥ C语言最短路径算法问题，Floyd算法行不通
要用算法你也要先理解了再用啊，不懂你是修改了什么，反正floyd肯定不是你这么写，floyd要把中间结点的遍历放在最三重循环的最外层。另外，求最短路径是怎么走的完全可以在更新最短路径长度的过程中记录中间结点是什么，这并非算法不能解决，而在于使用算法的人是否真正懂得算法过程，以及待解决的问题是否需要求解这方面的问题。
⑦ 求floyd最短路径算法，c语言代码；
就是一个三重循环，核心代码就这几行
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]>(A[i][k]+A[k][j]))
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
⑧ C++ 弗洛伊德算法
#include<cstdio>
#include<cstdlib>
using namespace std;
int map[105][105];
int main()
{
int m,n,i,j,k,x,y,a,b,t;
scanf("%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=999999999;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&t);
map[x][y]=t;
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(map[i][j]>map[i][k]+map[k][j])
map[i][j]=map[i][k]+map[k][j];
}
}
}
scanf("%d%d",&a,&b);
printf("%d ",map[a][b]);
system("pause");
return 0;
}
第8行的scanf("%d",&n,&m);这里是不是写错了？
⑨ floyd算法的c程序代码
#include<fstream>
#define Maxm 501
using namespace std;
ifstream fin("APSP.in");
ofstream fout("APSP.out");
int p,q,k,m;
int Vertex,Line[Maxm];
int Path[Maxm][Maxm],Map[Maxm][Maxm],Dist[Maxm][Maxm];
void Root(int p,int q)
{
if (Path[p][q]>0)
{
Root(p,Path[p][q]);
Root(Path[p][q],q);
}
else
{
Line[k]=q;
k++;
}
}
int main()
{
memset(Path,0,sizeof(Path));
memset(Map,0,sizeof(Map));
memset(Dist,0,sizeof(Dist));
fin >> Vertex;
for(p=1;p<=Vertex;p++)
for(q=1;q<=Vertex;q++)
{
fin >> Map[p][q];
Dist[p][q]=Map[p][q];
}
for(k=1;k<=Vertex;k++)
for(p=1;p<=Vertex;p++)
if (Dist[p][k]>0)
for(q=1;q<=Vertex;q++)
if (Dist[k][q]>0)
{
if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q))
{
Dist[p][q]=Dist[p][k]+Dist[k][q];
Path[p][q]=k;
}
}
for(p=1;p<=Vertex;p++)
{
for(q=p+1;q<=Vertex;q++)
{
fout << "\n==========================\n";
fout << "Source:" << p << '\n' << "Target " << q << '\n';
fout << "Distance:" << Dist[p][q] << '\n';
fout << "Path:" << p;
k=2;
Root(p,q);
for(m=2;m<=k-1;m++)
fout << "-->" << Line[m];
fout << '\n';
fout << "==========================\n";
}
}
fin.close();
fout.close();
return 0;
}
⑩ 如何利用弗洛伊德算法求多源最短路径问题c语言
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(f[i][j]>f[i][k]+f[k][j])
f[i][j]=f[i][k]+f[k][j];