Floyd's All Pairs Shortest Path Algorithm
by L. Shyamal
Environment: C++ (any variety)
Introduction
Graph algorithms work on nodes and edges. Nodes and edges are represented in many ways. This well-known algorithm uses a connectivity matrix. The matrix is a square matrix with the number of columns and rows the same as there are Nodes. The diagonal elements are set to zero. The offdiagonals are 1 if connected and 0 if not connected. (You could also use distances if you are dealing with something like road distances.)
The output of the algorithm is a matrix of the shortest distances between every pair of points. Notice that I am using a one-dimensional, linear array to represent matrices because this does not lead to any problems in memory allocation or differences across compilers.
The Code
// Floyd's All pairs shortest path algorithm (O (n^3) )
// input is adjacency matrix output is matrix of shortest paths
// C is the adjacency matrix
// n is the order of the square matrix
// A is the all pairs shortest paths matrix
// we assume that A is allocated by the caller
int GraphAlgo::ComputeFloydAPSP(int *C, int n, int *A)
{
int i,j,k;
// set all connected positions to 1
// and all unconnected positions to infinity
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
if ( *(C+i*n+j) == 0)
{
*(A+i*n+j) = 999999999; // does this look like infinity ?
}
else
{
*(A+i*n+j) = 1;
}
}
}
// set the diagonals to zero
for (i=0; i<n; i++)
{
*(A+i*n+i) = 0;
}
// for each route via k from i to j pick
// any better routes and replace A[i][j]
// path with sum of paths i-k and j-k
for (k=0; k<n; k++)
{
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
if ( *(A+i*n+k) + *(A+k*n+j) < *(A+i*n+j) )
{
// A[i][j] = A[i][k] + A[k][j];
*(A+i*n+j) = *(A+i*n+k)+ *(A+k*n+j);
}
}
}
}
return 0;
} // Floyd's algorithm
// this is for testing Floyd's algorithm
// demonstrates the allocation and
// deallocation of memory for the matrices
void FloydTest()
{
// allocate the entire matrix in one linear array
// trying to allocate it as an array of pointers to arrays
// didnt quite work, possibly because the [] and * notation
// arent quite replaceable
int n=4;
int *C=new int[n*n];
C[0]=0; C[1]=1; C[2]=0; C[3]=0;
C[4]=1; C[5]=0; C[6]=1, C[7]=0;
C[8]=0; C[9]=1; C[10]=0;C[11]=1;
C[12]=0;C[13]=0;C[14]=1;C[15]=0;
int* A = new int[n*n];
ComputeFloydAPSP (C,n,A);
printf("Final shortest distances\n");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
printf("%d ",*(A+i*n+j));
}
printf("\n");
}
printf("End of All pairs Shortest paths\n");
delete [] A;
delete [] C;
} // end of FloydTest
|
|
