Implementation of Warshal’s Algorithm in C to find Path Matrices of a Graph

Warshal’s Algorithm can be applied to find the Path Matrices and this the TRANSITIVE CLOSURE of a graph given its adj matrix. Warshal’s algorithm is based on the fact that the Path_k+1[i][j] is TRUE if and only if any one of the following conditions is true –

1) Path_k[i][j] == TRUE
2) Path_k[i][k+1] == TRUE && Path_k[k+1][j] == TRUE

i.e. Path_k+1[i][j] == Path_k[i][j] || Path_k[i][k+1] && Path_k[k+1][j] –

………. where Path_k+1[i][j] gives the path matrix for (k+1) nodes. The algorithm could be implemented as a C routine as shown bellow –

/* Routine to find Path Matrices and thus transitive closure of a graph given its adjacency matrix*/

void transclose(int adj[][MAXNODES], int path[][MAX]){

           int i, j, k;

           for(i=0; i< MAXNODES; i++) { 
               for(j=0; j< MAXNODES; j++) { 
                   path[i][j] = adj[i][j]; /* Path Matrix is first initialized to adj matrix
               }
           } 

           for(k=0; k< MAXNODES; k++) { 
               for(i=0; i< MAXNODES; i++) { 
                   if( path[i][k] == TRUE) {
                       for(j = 0; j < MAXNODES; j++){
                            path[i][j] = adj[i][j] || path[k][j]
                       }
                   }                    
               }
               printf("Transclose is > ", path[i][j]);
           } 

}