C Program To Implement Warshall’s Algorithm To Find Path Matrix
Learn how to Implement Warshall’s Algorithm to find path matrix in C programming. Alternatively, we can find path matrix of any graph by using powers of an Adjacency Matrix. However, Warshall’s Algorithm provides an efficient technique for finding path matrix of a graph.
The Warshall Algorithm is also known as Floyd – Warshall Algorithm, Roy – Warshall, Roy – Floyd or WFI Algorithm. It is a type of Dynamic Programming. It is basically used to find shortest paths in a weighted graph with non – zero edge weights. The Warshall algorithm is an efficient algorithm to compute compute paths between all pairs of vertices in dense graphs.
Must Read: C Program For N Queen’s Problem Solution
C Program To Implement Warshall’s Algorithm to Find Path Matrix
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 | #include<stdio.h> #define LIMIT 100 void show(int mat[LIMIT][LIMIT], int n); void new_graph(); int adjacency_matrix[LIMIT][LIMIT]; int n; int main() { int P[LIMIT][LIMIT]; int i, j, k; new_graph(); printf("\nadjacency_matrixacency Matrix\n"); show(adjacency_matrix, n); for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { P[i][j] = adjacency_matrix[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("P%d is: \n", k); show(P, n); } printf("P%d is the path matrix of the given graph\n", k - 1); return 0; } void show(int mat[LIMIT][LIMIT], int n) { int i, j; for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { printf("%3d", mat[i][j]); } printf("\n"); } } void new_graph() { int count, maximum_edges, origin, destination; printf("Enter Total Number of Vertices:\t"); scanf("%d", &n); maximum_edges = n * (n - 1); for(count = 1; count <= maximum_edges; count++) { printf("\nCo - Ordinates for Edge No. %d [(-1 -1) To Quit]:\t", count); printf("\nEnter Origin Point:\t"); scanf("%d", &origin); printf("\nEnter Destination Point:\t"); scanf("%d", &destination); if((origin == -1) && (destination == -1)) { break; } if(destination >= n || origin < 0 || origin >= n || destination < 0) { printf("Invalid Edge Input:\n"); count--; } else { adjacency_matrix[origin][destination] = 1; } } } |
Must Read: C Program For Banker’s Algorithm in Operating System
Output
In case you get any Compilation Errors or any doubts in this Code To Find Path Matrix using Warshall’s Algorithm in C Programming, let us know about it in the Comment Section below.
Can you enlist other algorithms to find Path matrix?
Yes. Ofcourse. Here is the list of some of the frequently used algorithms to compute the path matrix. There could be many more algorithms apart from these.
Thanks for the explanation and program for Warshall. Looking forward to learn more from this website.
This explanation for warshalls algorithm is quite easy to understand.
Dijkstra’s algorithm is much better than warshall’s algorithm to find path matrix.
P[i][j] = (P[i][j] || (P[i][k] && P[k][j]));
what does this do can you please explain??
brother please indent the code
Thank you so much! This Warshall code is just so simple and good.