Bellman-Ford: all shortest paths

问题:

I've successfully implemented Bellman-Ford to find the distance of the shortest path when edges have negative weights/distances. I've not been able to get it to return all shortest paths (when there are ties for shortest). I managed to get all shortest paths (between a given pair of nodes) with Dijkstra. Is this possible with Bellman-Ford? (just want to know if I'm wasting my time trying)

回答1:

If you alter the second step of the Bellman-Ford algorithm a little bit you can achieve something very similar:

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

where v.predecessor is a list of vertices. If the new distance of v equals a path which isn't included yet include the new predecessor.

In order to print all shortest paths you could use something like

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)

Use printPaths(stop,start,stop,stop.id) in order to print all paths.

Note: It is possible to exclude if u not in v.predecessor then v.predecessor += u from the modified algorithm if you remove duplicate elements after the algorithm has finished.