Shortest Path Matrix by Modified Warshall’s Algorithm
Write a C Program to find Shortest Path Matrix by Modified Warshall’s Algorithm. Here’s simple Program to find Shortest Path Matrix by Modified Warshall’s Algorithm in C Programming Language.
Modified 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 : : C Program to find Path Matrix by Warshall’s Algorithm
Below is the source code for C Program to find Shortest Path Matrix by Modified 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 Shortest Path Matrix by Modified Warshall's Algorithm */
#include<stdio.h>
#include<stdlib.h>
#define infinity 9999
#define MAX 100
int n;/*Number of vertices in the graph*/
int adj[MAX][MAX];/*Weighted Adjacency matrix*/
int D[MAX][MAX];/*Shortest Path Matrix*/
int Pred[MAX][MAX];/*Predecessor Matrix*/
void create_graph();
void FloydWarshalls( );
void findPath(int s, int d);
void display(int matrix[MAX][MAX], int n);
int main()
{
int s, d;
create_graph();
FloydWarshalls();
while(1)
{
printf("\nEnter source vertex(-1 to exit) : ");
scanf("%d",&s);
if(s == -1)
break;
printf("\nEnter destination vertex : ");
scanf("%d",&d);
if( s < 0 || s>n-1 || d<0 || d>n-1)
{
printf("\nEnter valid vertices \n\n");
continue;
}
printf("\nShortest path is : ");
findPath(s,d);
printf("\nLength of this path is %d\n",D[s][d]);
}
}/*End of main( )*/
void FloydWarshalls()
{
int i,j,k;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
if(adj[i][j] == 0)
{
D[i][j] = infinity;
Pred[i][j] = -1;
}
else
{
D[i][j] = adj[i][j];
Pred[i][j] = i;
}
}
for(k=0; k<n; k++)
{
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if( D[i][k] + D[k][j] < D[i][j] )
{
D[i][j] = D[i][k] + D[k][j];
Pred[i][j] = Pred[k][j];
}
}
printf("\nShortest path matrix is :\n");
display(D,n);
printf("\n\nPredecessor matrix is :\n");
display(Pred,n);
for(i=0;i<n;i++)
if(D[i][i]<0)
{
printf("\nError : negative cycle\n");
exit(1);
}
}/*End of FloydWarshalls()*/
void findPath(int s, int d)
{
int i, path[MAX], count;
if(D[s][d] == infinity)
{
printf("\nNo path \n");
return;
}
count = -1;
do
{
path[++count] = d;
d = Pred[s][d];
}while(d!=s);
path[++count] = s;
for(i=count; i>=0; i--)
printf("%d ",path[i]);
printf("\n");
}/*End of findPath()*/
void display(int matrix[MAX][MAX],int n )
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0; j<n; j++)
printf("%7d",matrix[i][j]);
printf("\n");
}
}/*End of display( )*/
void create_graph()
{
int i,max_edges,origin,destin, wt;
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;
printf("\nEnter weight for this edge : ");
scanf("%d",&wt);
if( origin >= n || destin >= n || origin<0 || destin<0)
{
printf("\nInvalid edge!\n");
i--;
}
else
adj[origin][destin] = wt;
}
}
OUTPUT : :
/* C Program to find Shortest Path Matrix by Modified Warshall's Algorithm */
Enter number of vertices : 6
Enter edge 1( -1 -1 to quit ) : 0 1
Enter weight for this edge : 3
Enter edge 2( -1 -1 to quit ) : 0 2
Enter weight for this edge : 1
Enter edge 3( -1 -1 to quit ) : 0 3
Enter weight for this edge : 2
Enter edge 4( -1 -1 to quit ) : 0 4
Enter weight for this edge : 1
Enter edge 5( -1 -1 to quit ) : 1 3
Enter weight for this edge : 4
Enter edge 6( -1 -1 to quit ) : 1 5
Enter weight for this edge : 3
Enter edge 7( -1 -1 to quit ) : 2 3
Enter weight for this edge : 1
Enter edge 8( -1 -1 to quit ) : 3 5
Enter weight for this edge : 2
Enter edge 9( -1 -1 to quit ) : 4 2
Enter weight for this edge : 3
Enter edge 10( -1 -1 to quit ) : -1 -1
Shortest path matrix is :
9999 3 1 2 1 4
9999 9999 9999 4 9999 3
9999 9999 9999 1 9999 3
9999 9999 9999 9999 9999 2
9999 9999 3 4 9999 6
9999 9999 9999 9999 9999 9999
Predecessor matrix is :
-1 0 0 0 0 3
-1 -1 -1 1 -1 1
-1 -1 -1 2 -1 3
-1 -1 -1 -1 -1 3
-1 -1 4 2 -1 3
-1 -1 -1 -1 -1 -1
Enter source vertex(-1 to exit) : 0
Enter destination vertex : 1
Shortest path is : 0 1
Length of this path is 3
Enter source vertex(-1 to exit) : 0
Enter destination vertex : 2
Shortest path is : 0 2
Length of this path is 1
Enter source vertex(-1 to exit) : 0
Enter destination vertex : 3
Shortest path is : 0 3
Length of this path is 2
Enter source vertex(-1 to exit) : 0
Enter destination vertex : 4
Shortest path is : 0 4
Length of this path is 1
Enter source vertex(-1 to exit) : 0
Enter destination vertex : 5
Shortest path is : 0 3 5
Length of this path is 4
Enter source vertex(-1 to exit) : 0
Enter destination vertex : 5
Shortest path is : 0 3 5
Length of this path is 4
Enter source vertex(-1 to exit) : 2
Enter destination vertex : 5
Shortest path is : 2 3 5
Length of this path is 3
Enter source vertex(-1 to exit) : 5
Enter destination vertex : 0
Shortest path is :
No path
Length of this path is 9999
Enter source vertex(-1 to exit) : -1
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 : :
- Path Matrix by Warshall’s Algorithm
- Path Matrix by powers of Adjacency matrix
- Program for Creation of Adjacency Matrix
- Shortest Path using Bellman Ford Algorithm