Bellman-Ford: all shortest paths

Question

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)

Mathematically, I'm not sure this is possible. If all of the edges have cost zero, for example, there are infinitely many possible shortest paths that you can take. Do you want shortest acyclic paths? — templatetypedef
Yes, sorry, should have specified that. I'd like to find all shortest acyclic paths between two nodes. — user1507844

Zeta Zeta · Accepted Answer · 2012-07-07T00:03:57

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.

Bellman-Ford: all shortest paths

1 Answers