1

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

2 回答 2

1

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

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

--L。

于 2012-06-11T09:11:04.103 回答
0

您发布的算法中的矩阵 P 是前驱矩阵。它列出了每条路径 i -> j 的前任。

这必须与距离矩阵一起计算：

  • P[i,j] 对于所有 i,j 都初始化为 NULL
  • 在 FW 的最内层循环中，如果您发现从节点 k 传递的较短路径（使用 P[k,j]），则更新 P[i,j]。

如果您发布距离的解决方案，我会更准确。

于 2013-05-06T21:58:57.667 回答