floyd算法中输出最短路径序列的C语言代码

本人已经用floyd算法编好了求有向图最短路径的程序，存储结构是矩阵，可是我实在想不出怎样输出每条最短路径的顶点序列，希望高手指教，不懂者勿扰。

void path(int i,int j)
{
int k;
if(P[i][j][i]==FALSE)
printf("There's no path!");
return;
for(k=0;k if(P[i][j][k]==TRUE)
{
path(i,k);
path(k,j);
break;
}
}
void print(){
int v,w,u,i;
for (v=0;v {
for (w=0;w printf(" %d ",D[v][w]);
printf("\n");
}
printf("Please input the tailvex v1 and headvex v2:");
scanf("v1=%d,v2=%d",&v,&w);
path(v,w);
}
以上两段应该对你有用。

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); } 这样只需调用out(a,b)即可输出a,b之间的最短路径节点序列. 说明一下,我对c并不熟悉,这些代码都是我凭印象写的,估计有不少语法错误,你就看做是伪代码好了.