algorithm - Bellman-Ford：所有最短路径

Question

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

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.predecessor是一个顶点列表。如果新的距离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,start,stop,stop.id)打印所有路径。

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