c - Floyd-Warshall 算法最短路径

Question

我实现了 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
    }
}

Answer 1

Floyd 的算法考虑了两个节点之间的所有路径，并保留到目前为止找到的最便宜的路径。您的代码以递归方式执行此操作。这是另一个在 C 中对此有很好解释的实现: http://www.fearme.com/misc/alg/node88.html

您也可以考虑 Dijkstra 算法，它可能对稀疏图表现更好。

--L.