C Program to find Path Matrix by Warshall’s Algorithm

Path Matrix by Warshall’s Algorithm

Write a C Program to find Path Matrix by Warshall’s Algorithm. Here’s simple Program to find Path Matrix by Warshall’s Algorithm in C Programming Language.

Warshall’s Algorithm

The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph.

Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).

A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices.

Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.

Also Read : : Insertion Deletion of Vertices and Edges in Graph using Adjacency list

Below is the source code for C Program to find Path Matrix by Warshall’s Algorithm which is successfully compiled and run on Windows System to produce desired output as shown below :

SOURCE CODE : :

/*  C Program to find Path Matrix by Warshall's Algorithm */

#include<stdio.h>
#define MAX 100

void display(int matrix[MAX][MAX], int n);
int adj[MAX][MAX];
int n;
void create_graph();

int main()
{
        int i,j,k;
        int P[MAX][MAX];

        create_graph();
        printf("\nThe adjacency matrix is :\n");
        display(adj,n);

        for(i=0; i<n; i++)
           for(j=0; j<n; j++)
                 P[i][j] = adj[i][j];

        for(k=0; k<n; k++)
        {
                for(i=0; i<n; i++)
                  for(j=0; j<n; j++)
                      P[i][j] = ( P[i][j] || ( P[i][k] && P[k][j] ) );
                printf("\nP%d is :\n",k);
                display(P,n);
        }
        printf("\nP%d is the path matrix of the given graph\n",k-1);
}/*End of main() */

void display(int matrix[MAX][MAX],int n)
{
        int i,j;
        for(i=0; i<n; i++)
        {
                for(j=0; j<n; j++)
                        printf("%3d",matrix[i][j]);
                printf("\n");
        }
}/*End of display()*/

void create_graph()
{
        int i,max_edges,origin,destin;

        printf("\nEnter number of vertices : ");
        scanf("%d",&n);

        max_edges = n*(n-1);

        for( i=1; i<=max_edges; i++ )
        {
                printf("\nEnter edge %d( -1 -1 ) to quit : ",i);
                scanf("%d %d",&origin,&destin);
                if((origin == -1) && (destin == -1))
                        break;
                if( origin >= n || destin >= n || origin<0 || destin<0)
                {
                        printf("\nInvalid edge!\n");
                        i--;
                }
                else
                        adj[origin][destin] = 1;
        }/*End of for*/
}/*End of create_graph()*/

OUTPUT : :

/*  C Program to find Path Matrix by Warshall's Algorithm  */

Enter number of vertices : 4

Enter edge 1( -1 -1 ) to quit : 0 1

Enter edge 2( -1 -1 ) to quit : 0 2

Enter edge 3( -1 -1 ) to quit : 0 3

Enter edge 4( -1 -1 ) to quit : 1 3

Enter edge 5( -1 -1 ) to quit : 2 3

Enter edge 6( -1 -1 ) to quit : -1 -1

The adjacency matrix is :
  0  1  1  1
  0  0  0  1
  0  0  0  1
  0  0  0  0

P0 is :
  0  1  1  1
  0  0  0  1
  0  0  0  1
  0  0  0  0

P1 is :
  0  1  1  1
  0  0  0  1
  0  0  0  1
  0  0  0  0

P2 is :
  0  1  1  1
  0  0  0  1
  0  0  0  1
  0  0  0  0

P3 is :
  0  1  1  1
  0  0  0  1
  0  0  0  1
  0  0  0  0

P3 is the path matrix of the given graph

Process returned 0

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.

Thanks for reading the post…

Path Matrix by Warshall’s Algorithm

Warshall’s Algorithm

SOURCE CODE : :

OUTPUT : :

Recommended Posts : :