我有一个关于贝尔曼福特算法的问题我创建了这个程序，当给定一个图形时，它将输出源节点和所有其他节点之间的最短距离那部分工作得很好，所以我有这样的输出：
The cost table is:
Destination: 0 1 2
Cost: 0 4 6
例如，我的源和节点2之间的最短距离是6，这是很大的。但现在我想得到实际的路线，而不仅仅是他们的成本。比如说，从s到v的路线的费用不是只有5，而是s->b->v。这可能是使用贝尔曼福特还是我遗漏了一部分？
非常感谢你。
最佳答案
这是可能的。
实现这一目标的一种方法是，在构建表的同时，不要只设定价格，而是使用另一个映射：node->node，让它成为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]