如何找到贝尔曼-福特的实际路径？
如何找到贝尔曼-福特的实际路径？
提问于 2013-12-04 09:34:23
关于行李员福特算法我有个问题。我创建了这个程序，当给定一个图时，它将输出源节点和所有其他节点之间的最短距离。这个部分工作得很棒，所以我有这样的输出：
The cost table is:
Destination: 0 1 2
Cost: 0 4 6例如，我的源和节点2之间的最短距离是6，这很好。但现在我想要的是实际的路线，而不仅仅是他们的成本。就像从s到v的路线上的费用是5，我想要这样的路线是s-> b -> v，是完全可以使用行李员福特，还是我遗漏了其中的一部分？
非常感谢。
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-12-04 11:03:17
这是可能的。
实现这一目标的一种方法是，在构建表时--而不是仅仅设置价格--拥有另一张地图:节点-->Node，让它是parent --当您在松弛路径中找到一条较短的路径时，也可以在parent地图中显示它。
伪代码(来自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完成后，只需按照地图从目标到源，以获得您的实际路径(当然，反向)。
要从地图上提取路线：
current := target
path := [] //empty list
while current != null:
path.addFirst(current)
current := predecessor[current]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20371647
复制相关文章
相似问题
腾讯云开发者
