如何获得Bellman-Ford找到的实际路径 [英] How to get the actual path found by Bellman-Ford

问题描述

我对Bellman ford算法有疑问.我创建了这个程序，当给出一个图时，它将输出源节点和所有其他节点之间的最短距离.那部分工作得很棒，所以我有这样的输出:

I have a question regarding the bellman ford algorithm. I created this program that when given a graph will output the shortest distance between a source node and all other nodes. That part is working fantastic so I have outputs like this:

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

例如，我的源与节点2之间的最短距离为6，这很棒.但是现在我想获得实际的路线，而不仅仅是它们的费用.就像在路线上从s到v的成本不是5一样，我希望路线是s-> b-> v.使用Bellman ford完全有可能吗?还是我错过了其中的一部分?

So for instance the shortest distance between my source and node 2 is 6,which is great. But now I would like to get the actual routes instead of just their costs. Like instead of having only the cost on the route from s to v is 5, I would like something like the route is s-> b -> v. Is that at all possible using bellman ford or am I missing some part of it ?

非常感谢.

推荐答案

可能.

一种实现方法是在构建表格时-不仅设置价格，还有另一张地图:Node-> Node，让它成为 parent -当您找到较短的路径时，在松弛路径中-在 parent 映射中也要指明它.

One way of achieving it is while you build the table - instead of only setting price, have another map:Node->Node, let it be parent - and when you found a shorter path, in the relaxation path - also make an indication of it in the parent map.

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

Pseudo code (from wikipedia):

   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

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

After you are done, just follow the map from target to source to get your actual path (reversed of course).

要从地图中提取路线，请执行以下操作:

To pull the route from the map:

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

这篇关于如何获得Bellman-Ford找到的实际路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！