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 Pathk+1[i][j] is TRUE if and only if any one of the following conditions is true –

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

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

………. where Pathk+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]);
           } 

}

Add a Comment

Your email address will not be published. Required fields are marked *