![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675334232013-Floyd%20Warshall%20Algorithm.jpg\")
<\/p>\n<\/p>\n
The Floyd Warshall algorithm in C is a dynamic programming approach used to find the shortest path between all pairs of vertices in a weighted graph. It is applicable to both directed and undirected graphs, with the exception of graphs that contain negative weight cycles. This algorithm proves to be the best choice when searching for the shortest path across every pair of vertices in a graph, such as finding the shortest routes between cities in a state or country. In this article, we will explore the workings of the Floyd Warshall algorithm in C and delve into its implementation details. We will also discuss its time complexity compared to other popular algorithms like Bellman-Ford and Dijkstra’s shortest path algorithm, highlighting why Floyd Warshall is often the preferred option. Additionally, we will explore the various applications of the Floyd-Warshall algorithm, showcasing its versatility and practical uses in different scenarios.<\/p>\n
Floyd-Warshall Algorithm is an algorithm which follows dynamic programming approach to find the shortest path between all the pairs of vertices in a weighted graph. This algorithm works well for both the directed and undirected weighted graphs. But, it does not work for graphs that contain negative weight cycles.<\/p>\n
If you\u2019re looking for an algorithm for scenarios like finding the shortest path between every pair of cities in a state or in a country, then the best man at work is our polynomial-time Floyd-Warshall algorithm.<\/p>\n
In other words, the Floyd-Warshall algorithm is the best choice for finding the shortest path across every pair of vertex in a graph.<\/p>\n
One restriction we have to follow is that the graph shouldn\u2019t contain any negative weight cycles.<\/p>\n
You see, the Floyd-Warshall algorithm does support negative weight edges in a directed graph so long the weighted sum of such edges forming a cycle isn\u2019t negative.<\/p>\n
And that\u2019s what here means by a negative weight cycle.<\/p>\n
If there exists at least one such negative weight cycle, we can always just keep traversing this cycle over and over while making the length of the path smaller and smaller. Keep repeating it, and the length at some point reaches negative infinity which is wildly unreasonable.<\/p>\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675334232295-Floyd%20Warshall%20Algorithm1.png\")
<\/p>\n
Also if we notice, the algorithm cannot support negative weight edges in an undirected graph at all. Such an edge forms a negative cycle in and of itself since we can traverse back and forth along that edge infinitely as it\u2019s an undirected graph.<\/p>\n
Well, you may suspect why we are learning another algorithm when we can solve the same thing by expanding the Bellman-Ford or Dijkstra\u2019s shortest path algorithm on every vertex in the graph.<\/p>\n
Yes, you can, but the main reason why we are not using Bellman-Ford or Dijkstra\u2019s shortest path algorithm is their Time complexity which we will discuss later in this article.<\/p>\n
Now that we have developed a fair understanding as to what is and why we use the Floyd-Warshall algorithm, let\u2019s take our discussion ahead and see how it actually works.<\/p>\n
Points to Remember:<\/strong><\/p>\n Given Graph:<\/p>\n Follow the steps mentioned below to find the shortest path between all the pairs of vertices:<\/p>\n Step 1:<\/strong> Step 2:<\/strong> Let k be the intermediate vertex on the shortest path from source to destination. k is the 0th vertex (i.e k = 0) in this stage. If (A[i][j] > A[i][k] + A[k][j]), A[i][j] is filled with (A[i][k] + A[k][j]).<\/p>\n In other words, if the direct distance between the source and the destination is larger than the path through the vertex k, the cell is filled with A[i][k] + A[k][j].<\/p>\n This vertex k is used to compute the distance from the source vertex to the destination vertex.<\/p>\n<\/li>\n Step 3:<\/strong> k is the 1st vertex in this stage (i.e. k = 1). The remaining steps are similar to those in step 2.<\/p>\n For example: For A2[3,2], the direct distance from vertex 3 to 2 is infinity and the sum of the distance from vertex 3 to 2 through vertex k(i.e. from vertex 3 to vertex 1 and from vertex 1 to vertex 2) is 0. Since 0 is less than infinity, A2[3,2] is filled with 0.<\/p>\n<\/li>\n Step 4:<\/strong> Step 5:<\/strong> Now, let us try to implement the above steps in a code.<\/p>\n\n
How does Floyd Warshall Algorithm in C Work?<\/h2>\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675334232295-Floyd%20Warshall%20Algorithm2.png\")
<\/p>\n\n
\nCreate a matrix A0 of dimension V*V, where V is the number of vertices. The row and column are indexed as i and j, respectively. i and j are the graph’s vertices.
\nThe value of cell A[i][j] means the distance from the ith vertex to the jth vertex. If there is no path between the ith vertex and the jth vertex, the cell is left with infinity.<\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675334232333-Floyd%20Warshall%20Algorithm3.png\")
<\/p>\n<\/li>\n
\nNow, using matrix A0, construct matrix A1. The elements in the first column and row stay unchanged. The remaining cells are filled out as follows.<\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675334232334-Floyd%20Warshall%20Algorithm4.png\")
<\/p>\n
\nSimilarly, A2 is derived from A1. The elements in the second column and second row remain unchanged.<\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675334232338-Floyd%20Warshall%20Algorithm5.png\")
<\/p>\n
\nSimilarly, A3 and A4 matrices are also constructed.
\nWhen generating A3, k is a second vertex(i.e. K = 2) and k is a third vertex(i.e. K = 3) during the construction of A4.<\/p>\n<\/li>\n<\/ul>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675334232338-Floyd%20Warshall%20Algorithm6.png\")
<\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675334232339-Floyd%20Warshall%20Algorithm7.png\")
<\/p>\n\n
\nA4 displays the shortest path between any pair of vertices.<\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1675334232372-Floyd%20Warshall%20Algorithm8.png\")
<\/p>\n<\/li>\n<\/ul>\nImplementation of Floyd Warshall Algorithm in C<\/h2>\n\t\t\t\t\t\t