**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*== TRUE &&

_{k}[i][k+1]*Path*== TRUE

_{k}[k+1][j]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]); } }