How to get the actual path found by Bellman-Ford

Question

I have a question regarding the bellman ford algorithm. I created this program that when given a graph will output the shortest distance between a source node and all other nodes. That part is working fantastic so I have outputs like this:

The cost table is: 
Destination:   0    1   2   
Cost:          0    4   6

So for instance the shortest distance between my source and node 2 is 6,which is great. But now I would like to get the actual routes instead of just their costs. Like instead of having only the cost on the route from s to v is 5, I would like something like the route is s-> b -> v. Is that at all possible using bellman ford or am I missing some part of it ?

Thank you very much.

amit amit · Accepted Answer · 2013-12-04T11:03:17

It is possible.

One way of achieving it is while you build the table - instead of only setting price, have another map:Node->Node, let it be parent - and when you found a shorter path, in the relaxation path - also make an indication of it in the parent map.

Pseudo code (from wikipedia):

   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

After you are done, just follow the map from target to source to get your actual path (reversed of course).

To pull the route from the map:

current := target
path := [] //empty list
while current != null:
   path.addFirst(current)
   current := predecessor[current]

How to get the actual path found by Bellman-Ford

1 Answers