C Program to implement Warshall's algorithm
Program
#include<stdio.h>
#define INF 9999
void warshall(int[10][10], int);
void main()
{
int a[10][10], i, j, n;
printf("Enter the number of nodes:\n");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for(i = 1; i <= n; i++)
{
for(j = 1;j <= n; j++)
{
scanf("%d", &a[i][j]);
}
}
printf("The adjacency matirx is:\n");
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
printf("%d\t", a[i][j]);
}
printf("\n");
}
warshall(a, n);
}
void warshall(int p[10][10],int n)
{
int i, j, k;
for(k = 1; k <= n; k++)
{
for(j = 1; j <= n; j++)
{
for(i = 1; i <= n; i++)
{
if((p[i][j] == 0) && (p[i][k] == 1) && (p[k][j] == 1))
{
p[i][j] = 1;
}
}
}
}
printf("The path matrix is:\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 nodes:
5
Enter the adjacency matrix:
0
1
1
0
0
0
0
0
1
1
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
The adjacency matirx is:
0 1 1 0 0
0 0 0 1 1
0 1 0 0 0
0 0 1 0 1
0 0 0 0 0
The path matrix is:
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 0 0 0 0