C语言最短路径算法问题，Floyd算法行不通

Python014

C语言最短路径算法问题，Floyd算法行不通,第1张

要用算法你也要先理解了再用啊，不懂你是修改了什么，反正floyd肯定不是你这么写，floyd要把中间结点的遍历放在最三重循环的最外层。另外，求最短路径是怎么走的完全可以在更新最短路径长度的过程中记录中间结点是什么，这并非算法不能解决，而在于使用算法的人是否真正懂得算法过程，以及待解决的问题是否需要求解这方面的问题。

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)

}