shortest-path - 实际保存路线的全对最短路径算法？

Question

我正在尝试重写我创建的一个简单的网络负载模拟工具，这次使用 Boost 库来提高性能(并避免实现错误)。在原始程序中，我通过调用 Dijkstra 算法来计算网络中每个源节点的最短路径，所以当我发现有一个像 Johnson 的全对算法时我很高兴(我的图将相对稀疏， 我假设)。然而，该算法只返回一个距离矩阵，而我需要实际的路线——至少类似于 Dijkstra 的算法实现返回的前任 map 。有什么方法可以实现这一点，还是我应该返回为图中的每个顶点重复调用 Dijkstra？我整天都在四处寻找，但找不到任何东西，我想我只是想在回到迭代方法之前确定一下。

谢谢!

Answer 1

这是一个老问题，但我也在寻找这个问题的答案，我发现之前的答案有点含糊。

假设您有距离矩阵，并且您想找到从顶点 i 到顶点 j 的最短路径。顶点 i 有一组可能的后继者 N； i 的后继是 N 中 的顶点最小化 :

c(i,n) + d(n,j)

其中 c(i,n) 是 i 和邻居 n 之间的边的成本，d(n,j) 是距离矩阵给出的 n 和 j 之间的最短距离。您只需选择最小化上述方程的邻居 n，然后重复该过程，将 i 替换为 n，将 N 替换为 n 的邻居。