Last Updated on June 23, 2023 by Mayank Dham
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 BellmanFord and Dijkstra’s shortest path algorithm, highlighting why Floyd Warshall is often the preferred option. Additionally, we will explore the various applications of the FloydWarshall algorithm, showcasing its versatility and practical uses in different scenarios.
What is the Floyd Warshall Algorithm in C?
FloydWarshall 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.
If youâ€™re 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 polynomialtime FloydWarshall algorithm.
In other words, the FloydWarshall algorithm is the best choice for finding the shortest path across every pair of vertex in a graph.
One restriction we have to follow is that the graph shouldnâ€™t contain any negative weight cycles.
You see, the FloydWarshall algorithm does support negative weight edges in a directed graph so long the weighted sum of such edges forming a cycle isnâ€™t negative.
And thatâ€™s what here means by a negative weight cycle.
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.
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â€™s an undirected graph.
Well, you may suspect why we are learning another algorithm when we can solve the same thing by expanding the BellmanFord or Dijkstraâ€™s shortest path algorithm on every vertex in the graph.
Yes, you can, but the main reason why we are not using BellmanFord or Dijkstraâ€™s shortest path algorithm is their Time complexity which we will discuss later in this article.
Now that we have developed a fair understanding as to what is and why we use the FloydWarshall algorithm, letâ€™s take our discussion ahead and see how it actually works.
Points to Remember:
 Negative weight cycle graphs are graphs where the sum of the weights of edges in a cycle is negative).
 A weighted graph is a graph in which each edge has some weight(numerical value) associated with it.
How does Floyd Warshall Algorithm in C Work?
Given Graph:
Follow the steps mentioned below to find the shortest path between all the pairs of vertices:

Step 1:
Create 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.
The 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. 
Step 2:
Now, using matrix A0, construct matrix A1. The elements in the first column and row stay unchanged. The remaining cells are filled out as follows.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]).
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].
This vertex k is used to compute the distance from the source vertex to the destination vertex.

Step 3:
Similarly, A2 is derived from A1. The elements in the second column and second row remain unchanged.k is the 1st vertex in this stage (i.e. k = 1). The remaining steps are similar to those in step 2.
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.

Step 4:
Similarly, A3 and A4 matrices are also constructed.
When 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.

Step 5:
A4 displays the shortest path between any pair of vertices.
Now, let us try to implement the above steps in a code.
Implementation of Floyd Warshall Algorithm in C
// Implementation of FloydWarshall Algorithm in C++ #include <iostream> using namespace std; // defining the number of vertices #define V 4 #define INF 9999 void printMatrix(int matrix[][V]); // Implementing floyd warshall algorithm void floydWarshall(int graph[][V]) { int matrix[V][V], i, j, k; for (i = 0; i < V; i++) for (j = 0; j < V; j++) matrix[i][j] = graph[i][j]; // Adding vertices individually for (k = 0; k < V; k++) { for (i = 0; i < V; i++) { for (j = 0; j < V; j++) { if (matrix[i][k] + matrix[k][j] < matrix[i][j]) matrix[i][j] = matrix[i][k] + matrix[k][j]; } } } printMatrix(matrix); } void printMatrix(int matrix[][V]) { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if(i==j){ continue; } else if (matrix[i][j] == INF){ cout<<"no path exist between "<<i<<" and "<<j<<endl; } else{ cout<<"shortest path from "<<i<<" to "<<j<<" is "<<matrix[i][j]<<endl; } } } } int main() { int graph[V][V] = {{0,INF,3,INF}, {5,0,4,INF}, {INF,INF,0,3}, {INF,2,INF,0}}; floydWarshall(graph); return 0; // End of Program }
Output:
shortest path from 0 to 1 is 2
shortest path from 0 to 2 is 3
shortest path from 0 to 3 is 0
shortest path from 1 to 0 is 5
shortest path from 1 to 2 is 2
shortest path from 1 to 3 is 5
shortest path from 2 to 0 is 6
shortest path from 2 to 1 is 1
shortest path from 2 to 3 is 3
shortest path from 3 to 0 is 3
shortest path from 3 to 1 is 2
shortest path from 3 to 2 is 0
Now, let’s discuss the time complexity of the Floyd warshall algorithm.
Time Complexity Analysis of the Floyd Warshall Algorithm
The overall time complexity of the Floyd Warshall algorithm is O(V^3) where V represents the number of vertexes in the graph. Let’s dive into more details in the time complexity analysis of the Floyd warshall algorithm.
Since we are discussing time complexity, letâ€™s move our discussion in the direction of why BellmanFord or Dijkstraâ€™s shortest path algorithm is not a good choice for solving the shortest path problem concerning all pairs of vertices.
The BellmanFord and Dijkstraâ€™s shortest path algorithm only computes the shortest path from one vertex to all other vertexes and has an upper bound of O(VE) and O(V + ElogV) where V and E denote the numbers of vertex and edges in the graph.
One more point to note about Dijkstraâ€™s shortest path algorithm is that it doesnâ€™t work for negatively weighted edges.
And if we expand the BellmanFord algorithm for all vertexes, the time complexity becomes V O(V E) but since the Floyd Warshall algorithm depends only on the number of vertexes, not on the number of edges in the graph.
This makes the FloydWarshall algorithm an ideal choice for us.
Applications of the Floyd Warshall Algorithm in C
Here are some applications of the Floyd warshall algorithm:
 Performs fast computation of Pathfinder networks.
 Helps in finding the Inversion of real matrices.
 Helps in finding the transitive closure of directed graphs.
 Helps in finding out if an undirected graph is bipartite or not.
 Used in finding the shortest path in the graph.
Conclusion
In conclusion, the FloydWarshall algorithm in C is a powerful tool for finding the shortest path between all pairs of vertices in a weighted graph. Its dynamic programming approach makes it suitable for various scenarios, including route planning, transitive closure determination, bipartite graph identification, and more. Unlike other algorithms like BellmanFord or Dijkstra’s shortest path algorithm, FloydWarshall offers a time complexity of O(V^3), making it an efficient choice when dealing with large graphs. However, it is important to note that the algorithm cannot handle graphs with negative weight cycles. Despite this limitation, the FloydWarshall algorithm proves to be a valuable tool in solving complex shortest path problems. By understanding its inner workings and implementing it in C, developers can harness its capabilities for a wide range of applications in graph theory and optimization.
Frequently Asked Questions (FAQs)
Q1. Can the FloydWarshall algorithm handle graphs with negative weight cycles?
No, the FloydWarshall algorithm cannot handle graphs that contain negative weight cycles. It assumes that there are no negative weight cycles in the graph for accurate shortest path calculations.
Q2. Is the FloydWarshall algorithm suitable for both directed and undirected graphs?
Yes, the FloydWarshall algorithm can be applied to both directed and undirected graphs. However, it cannot handle negative weight edges in undirected graphs since they inherently create negative cycles.
Q3. How does the FloydWarshall algorithm compare to BellmanFord and Dijkstra’s shortest path algorithm in terms of time complexity?
The FloydWarshall algorithm has a time complexity of O(V^3), where V represents the number of vertices. In contrast, BellmanFord has a time complexity of O(VE), and Dijkstra’s algorithm has a time complexity of O(V + ElogV). FloydWarshall’s dependency only on the number of vertices makes it an ideal choice for solving the shortest path problem across all pairs of vertices.
Q4. What are some applications of the FloydWarshall algorithm?
The FloydWarshall algorithm finds utility in various applications, including the computation of Pathfinder networks, inversion of real matrices, determination of transitive closure in directed graphs, identification of bipartite graphs, and finding the shortest path in a graph.
Q5. Can the FloydWarshall algorithm handle weighted graphs where each edge has different weights?
Yes, the FloydWarshall algorithm can handle weighted graphs with varying edge weights. It considers the weights assigned to each edge while calculating the shortest path between vertices. The algorithm constructs a matrix that stores the distances between all pairs of vertices, taking into account the individual weights of the edges.