Warshall’s algorithm:
The transitive closure of a directed graph with n vertices can be defined as the n-by-n boolean matrix T={tij}, in which the element in the ith row(1<=i<=n) and jth column(1<=j<=n) is 1 if there exists a non trivial directed path from ith vertex to jth vertex, otherwise, tij is 0. Warshall‟s algorithm constructs the transitive closure of a given digraph with n vertices through a series of n-by-n boolean matrices: R(0) ,….,R(k-1) , R(k) ,….,R(n) where, R(0) is the adjacency matrix of digraph and R(1) contains the information about paths that use the first vertex as intermediate. In general, each subsequent matrix in series has one more vertex to use as intermediate for its path than its predecessor. The last matrix in the series R(n) reflects paths that can use all n vertices of the digraph as intermediate and finally transitive closure is obtained. The central point of the algorithm is that we compute all the elements of each matrix R(k) from its immediate predecessor R (k-1) in series
Complexity: The time efficiency of Warshall‟s algorithm is in Θ (n3).
# include <stdio.h>
# include <conio.h>
int n,a[10][10],p[10][10];
void path()
{
int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
p[i][j]=a[i][j];
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(p[i][k]==1&&p[k][j]==1)
p[i][j]=1;
}
void main()
{
int i,j;
clrscr();
printf("Enter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
path();
printf("\nThe path matrix is showm below\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d ",p[i][j]);
printf("\n");
}
getch();
}
