我实现了 Floyd-Warshall 算法。根据他们的矩阵,我可以得到正确的结果,关于两个地方之间的最短路径和他们的距离。我的问题是如何打印从 i 到 j 的最短距离。我做了一些研究,发现了一个类似的算法。任何人都可以向我解释它应该如何,或者它是如何工作的,或者说任何其他建议?
PrintShortestPath(P,i,j){
if(i==j) print i
else if (P[i][j]==NULL)
print "No path from i to j"
else{
PrintShortestPath(P,i,P[i][j])
print j
}
}
最佳答案
Floyd 的算法考虑了两个节点之间的所有路径,并保留到目前为止找到的最便宜的路径。 您的代码以递归方式执行此操作。 这是另一个在 C 中对此有很好解释的实现: http://www.fearme.com/misc/alg/node88.html
您也可以考虑 Dijkstra 算法,它可能对稀疏图表现更好。
--L.
关于c - Floyd-Warshall 算法最短路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10976498/