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 : :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
/* 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 : :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
/* 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