__Program Statement :__Write a C program to implement Warshall's algorithm to produce reachability matrix of a directed graph.

__Theory :__Warshall's algorithm is one of the shortest path algorithms in graph theory. By this classical algorithm we can determine whether there is a path from any vertex vi to another vertex vj either directly or through one or more intermediate vertices. In other words we can test the reachability of all pairs of vertices in a graph. A directed graph is taken as input in the form of a vertex by vertex binary matrix such that w(i,j) = 0 if vertices vi and vj has no direct path between them and w(i,j) = 1 if there is a direct path from vi to vj. The output of the algorithm is also a binary matrix of same order as input where we can find reachability between all pair of vertices. Three for loops are used in the program and the number of times the outermost loop iterates is same as the number of vertices in the graph. For example - if number of vertices are 5 then we get the output matrix after 5th iteration. For each iteration k, it decides whether there is a path from vi to vj either directly or via k i.e from vi to vk and then from vk to vj. It therefore sets the matrix entries to 0 or 1 accordingly.

__Algorithm :__Algo_warshall(w[size][size], n) /* The input graph and no. of vertices n passed as parameters */

{

For(k=1 to n) /* k represents table no. */

{

For(i=1 to n) /* i represents row no. within a table */

{

For(j=1 to n) /* j represents column no. within a row */

{

/*Exsisting 1 entries will be kept and 0 entries may or maynot be changed*/ w[i][j] = w[i][j] OR (w[i][k] AND w[k][j]);

}

}

}

}

/* End of Algo_warshall */

__Program listing :__/* C program to implement Warshall's algorithm which will produce reachability matrix of a directed graph */

#include<stdio.h>

#define size 10 /*Defining maximum size of the matrix*/

main()

{

int a[size][size];

int i,j,k,n;

void warshall(int[][j],int);

printf("Enter no. of vertices : ");/*Number of vertices should be less or equal to the defined size*/

scanf("%d",&n);

/*Enter 1 if ith vertex and jth vertex has directed path else enter 0*/

printf("Give the initial graph(in binary matrix form):n");

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

{

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

{

printf("Enter the value of a[%d][%d]:",i,j);

scanf("%d",&a[i][j]);

}

}

warshall(a,n);/* Function declaration*/

printf("The final matrix where we can find the presence of directed path :n");

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

{

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

printf("%5d",a[i][j]);

printf("n");

}

}

void warshall(int a[size][size],int n)/*Function definition*/

{

int k,i,j;

for(k=0;k<n;k++)/*n is the no.of vertices of the graph and k represents table no.*/

{

for(i=0;i<n;i++)/*i represents row no. within a table*/

{

for(j=0;j<n;j++)/*j represents column no. within a row*/

{

a[i][j]=a[i][j]||(a[i][k] && a[k][j]);/*Exsisting 1 entries will be kept and 0 entries may or maynot be changed*/

}

}

}

}

__Output :__Enter no. of vertices : 5

Give the initial graph(in binary matrix form):

Enter the value of a[0][0]:0

Enter the value of a[0][1]:1

Enter the value of a[0][2]:1

Enter the value of a[0][3]:0

Enter the value of a[0][4]:0

Enter the value of a[1][0]:0

Enter the value of a[1][1]:0

Enter the value of a[1][2]:0

Enter the value of a[1][3]:1

Enter the value of a[1][4]:1

Enter the value of a[2][0]:0

Enter the value of a[2][1]:1

Enter the value of a[2][2]:0

Enter the value of a[2][3]:0

Enter the value of a[2][4]:0

Enter the value of a[3][0]:0

Enter the value of a[3][1]:0

Enter the value of a[3][2]:1

Enter the value of a[3][3]:0

Enter the value of a[3][4]:1

Enter the value of a[4][0]:0

Enter the value of a[4][1]:0

Enter the value of a[4][2]:0

Enter the value of a[4][3]:0

Enter the value of a[4][4]:0

The final matrix where we can find the presence of directed path :

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

__Discussions :__● Number of vertices of the graph must be less than the defined size (or dimension) of the input weight-matrix.

● Weights of edges of the graph given as input must be non-negative real numbers otherwise it will not produce desirable result.

● The complexity of this algorithm is O(n3) and can be solved in polynomial time.

● We can also check existence of a circuit in a directed graph by this algorithm. If we get atleast one diagonal entry 1 in the output matrix then the graph has atleast one circuit.