Warshall Program

3. Compute the transitive closure of a given directed graph using Warshall’s algorithm.

#include<stdio.h>
void warshall(int a[10][10],int n);

void main()
{
 int a[10][10],i,j,n;
 printf("\n*********WARSHALL PROGRAM*******\n\n");
 printf("\n Enter the number of nodes in a graph\n");
 scanf("%d",&n);
 printf("\n\n Enter the adjacency matrix of directed graph\n");
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
 scanf("%d",&a[i][j]);
 printf("\n Entered adjacency matrix of ordered graph\n");
 for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
    {
     printf("%d\t",a[i][j]);
    }
   printf("\n");
  }
 warshall(a,n);
 printf("\n\nTransitive closure matrix is \n");
 for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
    {
     printf("%d\t",a[i][j]);
    }
   printf("\n");
  }
  printf("\n\n*********************************\n\n");
 }
 void warshall(int a[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++)
       {
      a[i][j]=a[i][j]||(a[i][k]&&a[k][j]);
       }
     }
   }
 }



OUTPUT:

Enter the number of nodes in a graph
3

Enter the adjacency matrix of directed graph
0  1  0  0  0  1  1  0  0