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)

Answer 2

A bit late but the above code is flawed .... it should not be next[i][j]=next[k][j] but the correct code for finding this is next[i][j]=next[i][k]

Try it yourself on a sample input and you will get to know why this works and why the previous one is wrong

Answer 3

Here is the below implementation. Why don't try a problem on it! Enjoy CP!!

   // g[][] is the graph
   // next[i][j] stores vertex next to i in the shortest path between (i,j)
      for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
          if(g[i][j]==0)g[i][j]=inf;  // there is no edge b/w (i,j)
          else next[i][j]=j;    // if there is an edge b/w i and j then j should be next to i
        }
      }

      for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++){
            if(g[i][j]>g[i][k]+g[k][j]){
              g[i][j]=g[i][k]+g[k][j];
              next[i][j]=next[i][k];  // we found a vertx k next to i which further decrease the shortest path b/w (i,j) so updated it
            }
          }
        }
      }
      // for printing path
      for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
          int u=i,v=j;
          print(u+" ");
          while(u!=v){
            u=next[u][v];
            print(u+" ");
          }
          print("\n");
        }
      }