Floyd-Warshall's

From VT.Prog

Much simpler than Dijkstra's for finding the shortest path from point A to point B, but in general does the same thing.

Code

Here is the simple version for when you don't need the path:

//2d array with dist[i][j] being the distance between point i
and point j.  when the algorithm is done, it should hold the
shortest distance between point i and j.
int dist[][];


for(k=1;k<n;k++)
   for(i=0;i<n;i++)
      for(j=0;j<n;j++)
         if(dist[i][j] > dist[i][k] + dist[k][j])
            dist[i][j] = dist[i][k] + dist[k][j];

//the order of these loops does matter:
//all you need to remember about the order is the part in the middle of
//the addition must be the outer most loop.

Generating the path

The modification of this algorithm required to generate the path in addition to the distance isn't very complicated either:

int dist[][];
//this new array is initialized with pred[i][j] = i
int pred[][];

for(k=1;k<n;k++)
   for(i=0;i<n;i++)
      for(j=0;j<n;j++)
         if(dist[i][j] > dist[i][k] + dist[k][j]) {
            dist[i][j] = dist[i][k] + dist[k][j];
            pred[i][j] = k;
         }


//then to loop through the pred list:
for(i=END;i!=BEGIN;i=pred[BEGIN][i])
       print i, pred[BEGIN][i]