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.

Answer 1

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]

Answer 2

C++ Code: The following code snippet is designed to work when the graph is given in the form of adjacency list.

GetPredecessors function's signature:

std::map<std::string, std::set<std::string>> <ClassName>::GetPredecessors()

Similarly

for (auto i = 0; i < data.size() - 1; ++i){  // parse n-1 times
    for (auto v = 0; v < data.size(); ++v){  // parse all nodes/vertices
        for (auto u : pre[idxintopstr[v]]) { // parse all the parents of each vertice 
            if(distance[v] > distance[idxidopint[u]] + CalculateDistance(idxintopstr[v], u)){
                distance[v] = distance[idxidopint[u]] + CalculateDistance(idxintopstr[v], u);
                parent[v] = idxidopint[u];
            } 
        }
    }
    if (i > 0 && distance_onepast == distance){    // implements early stopping
        break;
    }
    distance_onepast = distance;
}

Parent vector constructed doesn't includes the destination node (needs to be added manually.) Parent vector needs to be parsed and resultant vector shall have the shortest path in reverse order. You need to then just reverse the result to get the desired result.

References: https://github.com/ourarash/cpp_tour

More generalized for of the same answer:

for (auto i = 0; i < data.size() - 1; ++i){  // parse n-1 times
        for (auto v = 0; v < data.size(); ++v){  // parse all nodes/vertices
            for (auto u : pre[v]) { // parse all the parents of each vertice 
                if(distance[v] > distance[u] + CalculateDistance(v, u)){
                    distance[v] = distance[u] + CalculateDistance(v, u);
                    parent[v] = u;
                } 
            }
        }
        if (i > 0 && distance_onepast == distance){    // implements early stopping
            break;
        }
        distance_onepast = distance;
    }