如何获取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算法是否可能实现这一点，还是我遗漏了其某些部分？非常感谢。

- Niehm

Answer 1

这是可能的。

实现方式之一是在构建表格时，除了设定价格外，还有另一个映射：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]

- amit

---

我按照伪代码实现了它，也得到了地图，但是我似乎无法弄清楚如何提取路线。例如，如果我必须从我的起点到我的目的地经过3个节点，那么我该如何显示它们所经过的路线。我现在的做法似乎不正确，如果一个路线不是前一个路线的增量。谢谢。 - Niehm

Answer 2

C++ 代码： 以下代码片段设计为在以邻接表形式给出图时工作。

GetPredecessors 函数的签名：

std::map<std::string, std::set<std::string>> <ClassName>::GetPredecessors()

同样地

for (auto i = 0; i < data.size() - 1; ++i){  // parse n-1 times
    for (auto v = 0; v < data.size(); ++v){  // parse all nodes/vertices
        for (auto u : pre[idxintopstr[v]]) { // parse all the parents of each vertice 
            if(distance[v] > distance[idxidopint[u]] + CalculateDistance(idxintopstr[v], u)){
                distance[v] = distance[idxidopint[u]] + CalculateDistance(idxintopstr[v], u);
                parent[v] = idxidopint[u];
            } 
        }
    }
    if (i > 0 && distance_onepast == distance){    // implements early stopping
        break;
    }
    distance_onepast = distance;
}

父向量构建时不包括目标节点（需要手动添加）。需要解析父向量，并将结果向量按照最短路径的逆序排列。然后只需将结果反转即可获得所需结果。

参考资料：https://github.com/ourarash/cpp_tour 同一答案的更一般化形式：

for (auto i = 0; i < data.size() - 1; ++i){  // parse n-1 times
        for (auto v = 0; v < data.size(); ++v){  // parse all nodes/vertices
            for (auto u : pre[v]) { // parse all the parents of each vertice 
                if(distance[v] > distance[u] + CalculateDistance(v, u)){
                    distance[v] = distance[u] + CalculateDistance(v, u);
                    parent[v] = u;
                } 
            }
        }
        if (i > 0 && distance_onepast == distance){    // implements early stopping
            break;
        }
        distance_onepast = distance;
    }

- Singh