4

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

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

因此,例如,我的源和节点 2 之间的最短距离是 6,这很棒。但现在我想获得实际路线,而不仅仅是他们的成本。就像从 s 到 v 的路线上的成本不是 5 一样,我想要路线是 s-> b -> v 之类的东西。使用 bellman ford 是否有可能,还是我错过了其中的一部分?

非常感谢。

4

1 回答 1

2

有可能的。

实现它的一种方法是在构建表格时 - 而不是只设置价格,还有另一个地图:节点 - >节点,让它成为parent- 当你找到一条较短的路径时,在松弛路径中 - 也要指出它在parent地图中。

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

   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

完成后,只需按照从目标到源的地图获取您的实际路径(当然是相反的)。

从地图中拉出路线:

current := target
path := [] //empty list
while current != null:
   path.addFirst(current)
   current := predecessor[current]
于 2013-12-04T11:03:17.383 回答