algorithm - 如何获取 Bellman-Ford 找到的实际路径

Question

我有一个关于贝尔曼福特算法的问题。我创建了这个程序，当给定一个图时，它将输出源节点和所有其他节点之间的最短距离。这部分工作得非常好，所以我有这样的输出:

The cost table is: 
Destination:   0    1   2   
Cost:          0    4   6

例如，我的源和节点 2 之间的最短距离是 6，这很好。但现在我想得到实际的路线，而不仅仅是它们的成本。就像从 s 到 v 的路线成本不是只有 5 一样，我想要类似路线 s-> b -> v 的路线。使用 Bellman Ford 是否可以实现这一点，还是我遗漏了其中的某些部分？

非常感谢。

Answer 1

这是可能的。

实现这一目标的一种方法是在构建表时 - 而不是仅设置价格，而是使用另一个映射:Node->Node，让它成为 parent - 当您找到更短的路径时，在松弛路径中 - 也在父 map 中进行指示。

伪代码(来自维基百科):

   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

完成后，只需按照从目标到源的 map 即可获取实际路径(当然是相反的)。

要从 map 中提取路线:

current := target
path := [] //empty list
while current != null:
   path.addFirst(current)
   current := predecessor[current]