贝尔曼 - 福特:所有最短路径

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如果在算法完成后删除重复元素,则可以从修改后的算法中排除.