# 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]);
}

}
```