Warshall Algorithm

ALGORITHM Warshall(A[1..n, 1..n])

//Implements Warshall’s algorithm for computing the transitive closure
//Input: The adjacency matrix A of a digraph with n vertices
//Output: The transitive closure of the digraphR(0) ← Afor k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n doR(k)[i, j] ← R(k-1)[i, j] or (R(k-1)[i, k] and R(k-1)[k, j])return R(n)  

C program:

 #include<stdio.h>

 #include<math.h>

    int max(int,int);

    void warshal(int p[10][10],int n) {

        int i,j,k;

        for (k=1;k<=n;k++)

          for (i=1;i<=n;i++)

           for (j=1;j<=n;j++)

            p[i][j]=max(p[i][j],p[i][k]&&p[k][j]);

    }

int max(int a,int b) {

        if(a>b)

         return(a); else

         return(b);

    }

    void main() {

        int p[10][10]={0};

        int n,e,u,v,i,j;

        printf("\n Enter the number of vertices:");

        scanf("%d",&n);

        printf("\n Enter the number of edges:");

        scanf("%d",&e);

        for (i=1;i<=e;i++) {

                printf("\n Enter the start vertices of edge %d:",i);

                scanf("%d",&u);

                printf("\n Enter the end vertices of edge %d:",i);

                scanf("%d",&v);

                p[u][v]=1;

        }

        printf("\n Matrix of input data: \n");

        for (i=1;i<=n;i++) {

                for (j=1;j<=n;j++)

                   printf("%d\t",p[i][j]);

                printf("\n");

        }

        warshal(p,n);

        printf("\n Transitive closure: \n");

        for (i=1;i<=n;i++) {

                for (j=1;j<=n;j++)

                   printf("%d\t",p[i][j]);

                printf("\n");

        }

  }

Output:

 Enter the number of vertices:4

 Enter the number of edges:4

 Enter the start vertices of edge 1:1

 Enter the end vertices of edge 1:2

 Enter the start vertices of edge 2:2

 Enter the end vertices of edge 2:4

 Enter the start vertices of edge 3:4

 Enter the end vertices of edge 3:1

 Enter the start vertices of edge 4:4

 Enter the end vertices of edge 4:3

 Matrix of input data:

0       1       0       0

0       0       0       1

0       0       0       0

1       0       1       0

 Transitive closure:

1       1       1       1

1       1       1       1

0       0       0       0

1       1       1       1