8

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 ?

Amit Tomar
  • 4,800
  • 6
  • 50
  • 83
  • You should provide a short sample of the input and output of your code. Or at least provide a description of what the output you get look like. – Mr_Hic-up Nov 06 '13 at 13:49
  • There’s really no modification at all necessary – Floyd–Warshall’s algorithm gives you the shortest paths directly (the Wikipedia article is highly misleading; Robert Floyd’s formulation gave the length, Warshall’s gave the paths; together, they give both). But if you’re only interested in *one* shortest path, this algorithm isn’t appropriate anyway, there are more efficient ones (Dijkstra’s algorithm). – Konrad Rudolph Nov 06 '13 at 13:49
  • @KonradRudolph I am interested in printing the actual path and not the path length which normally Floyd Warshal provides, and hence the modification. – Amit Tomar Nov 06 '13 at 13:50
  • @Amit See my modified comment. The Wikipedia article is wrong, FW, in its canonical form, *does* provide both. – Konrad Rudolph Nov 06 '13 at 13:51

3 Answers3

8

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)
Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
  • What should I initialize the matrix `next[i][j]` with ? And the only place where this matrix is modified is the statement `next[i][j] ← next[k][j]`. Wouldn't it just keep on overwriting the default values from one location to another location of the same matrix ? – Amit Tomar Nov 06 '13 at 14:20
  • @Amit Good observation, forgot to mention that (although the linked page mentions that, albeit not in the pseudocode, just the Java implementation). I’ll add that, gimme a sec … – Konrad Rudolph Nov 06 '13 at 16:21
0

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

Shubham Kumar
  • 92
  • 1
  • 12
0

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");
        }
      }
lazy_propagator
  • 1
  • 1