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

Question

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

Answer 1

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);
}

Answer 2

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并不熟悉,这些代码都是我凭印象写的,估计有不少语法错误,你就看做是伪代码好了.本回答被提问者采纳