贝尔曼·福特：所有最短路径

Question

我已经成功地实现了Bellman-Ford，当边具有负权重/距离时，找到最短路径的距离。我无法让它返回所有最短路径（当最短路径有联系时）。我设法用Dijkstra获得所有最短的路径（给定的一对节点之间）。贝尔曼-福特有可能吗？（只是想知道我是否在浪费时间）

Answer 1

如果你稍微改变一下Bellman-Ford算法的第二步，你可以得到类似的结果：

for i from 1 to size(vertices)-1:
   for each edge uv in edges: // uv is the edge from u to v
       u := uv.source
       v := uv.destination
       if u.distance + uv.weight < v.distance:
           v.distance := u.distance + uv.weight
           v.predecessor[] := u
       else if u.distance + uv.weight == v.distance:
           if u not in v.predecessor:
               v.predecessor += u

其中v.preference是顶点列表。如果v的新距离等于尚未包含新前导的路径。

为了打印所有最短路径，您可以使用以下内容

procedure printPaths(vertex current, vertex start, list used, string path):
    if current == start:
        print start.id + " -> " + path
    else:
        for each edge ve in current.predecessors:
            if ve.start not in used:
                printPaths(ve.start,start, used + ve.start, ve.start.id + " -> " + path)

使用printPaths（停止，开始，停止，stop.id）以便打印所有路径。

注意：如果在算法完成后删除重复元素，则可以从修改后的算法中排除，如果u不在v.predecessorv.predecessor=u。