How to get the actual path found by Bellman-Ford

algorithm, bellman-ford

Solution

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]

Problem

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.

Original source