**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**

**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 : :**

**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 : :**

**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…**

**Recommended Posts : :**

**Recommended Posts : :**

- Path Matrix by powers of Adjacency matrix
- Insertion Deletion of Vertices and Edges in Graph
- Insert Delete Edges in a Directed graph using Adjacency Matrix
- Program for Creation of Adjacency Matrix

hello .

How can we implement the paths of cities in the Floyd algorithm with classes in ++ c?

Hello.

How can we implement the paths of cities in the Floyd algorithm with classes in ++ c?