C Program to implement Warshall’s Algorithm


Levels of difficulty: / perform operation:

Warshall’s algorithm enables to compute the transitive closure of the adjacency matrix of any digraph.


C Program

#include<stdio.h>
#include<conio.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
	}
	,n,e,u,v,i,j;
	clrscr();
	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 end vertices of edge %d:",i);
		scanf("%d%d",&u,&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");
	}
	getch();
}





Quantitative Aptitude
Reasoning
Programming
Interview