This article was contributed 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.

- L. Shyamal
Bangalore, India

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 

History

Comments:

• Floyd's All Pairs Shortest Path Algorithm - Debi Prasanna Patnaik (2003/04/30)
• And in VB have a a problems? - Cesar Sandoval (2002/11/17)
• Dear Dumbcum(Blond Dancom) - Sketch (2002/10/02)
• Nice try - yoav (2002/06/24)
• Suxx - Dancom (2002/06/17)
• infinity - Dominator (2002/06/16)
• No Comments - RINAT (2002/06/06)

Add Comment