Printing shortest path b/w given nodes using modified floyd warshall

Question

I read the approach given by Wikipedia to print the shortes path b/w two given points in a graph by modifying Floyd Warshall algorithm . I coded this, but its not really giving the expected output :

1. Initialize all the elements in minimumDistanceMatrix[i][j] to respective weights in the graph and all the elements in the matrix shortestPathCalculatorMatrix [i][j] to -1.

2. Then :

   // Find shortest path using Floyd–Warshall algorithm
   
   for ( unsigned int k = 0 ; k < getTotalNumberOfCities() ; ++ k)
      for ( unsigned int i = 0 ; i < getTotalNumberOfCities() ; ++ i)
         for ( unsigned int j = 0 ; j < getTotalNumberOfCities() ; ++ j)
             if ( minimumDistanceMatrix[i][k] + minimumDistanceMatrix[k][j] < minimumDistanceMatrix[i][j] )
             {
                   minimumDistanceMatrix[i][j] = minimumDistanceMatrix[i][k] + minimumDistanceMatrix[k][j];
                   shortestPathCalculatorMatrix [i][j] =  k;
             }
   

3. Then :

   void CitiesMap::findShortestPathListBetween(int source , int destination) 
   {
        if( source == destination || source < 0 || destination < 0)
           return;
   
        if( INFINITY == getShortestPathBetween(source,destination) )
           return ;
   
        int intermediate = shortestPathCalculatorMatrix[source][destination];
   
        if( -1 == intermediate )
        {
           pathCityList.push_back( destination );
           return ;
        }
   
        else
        {
           findShortestPathListBetween( source, intermediate ) ;
           pathCityList.push_back(intermediate);
           findShortestPathListBetween( intermediate, destination ) ;
   
           return ;
        }
   }
   

P.S: pathCityList is a vector which is assumed to be empty before a call to findShortestPathListBetween is made. At the end of this call, this vector has all the intermediate nodes in it.

Can someone point out where I might be going wrong ?

Answer 1

It’s much easier (and more direct) not to iterate over indices but over vertices. Furthermore, each predecessor (usually denoted π, not next), needs to point to its, well, predecessor, not the current temporary vertex.

Given a |V|×|V| adjacency matrix dist for the distances, initialised to infinity, and a |V|×|V| adjacency matrix next to with pointers to vertices,

for each vertex v
    dist[v, v] ← 0
for each edge (u,v)
    dist[u, v] ← w(u,v)  // the weight of the edge (u,v)
    next[u, v] ← u

for each vertex k
    for each vertex i
        for each vertex j
            if dist[i, k] + dist[k, j] < dist[i, j] then
                dist[i, j] ← dist[i, k] + dist[k, j]
                next[i, j] ← next[k, j]

Note that I’ve changed the three nested loops to iterate over vertices not indices, and I’ve fixed the last line to refer to the previous node rather than any intermediate node.

An implementation of the above which looks almost like the pseudocode can be found, for instance, in scipy.sparse.csgraph.

Path reconstruction starts at the end (j in the code below) and jumps to the predecessor of j (at next[i, j]) until it reaches i.

function path(i, j)
    if i = j then
        write(i)
    else if next[i, j] = NIL then
        write("no path exists")
    else
        path(i, next[i, j])
        write(j)