Floyd Warshall Algorithm

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 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.

What is the Floyd Warshall Algorithm in C?

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.

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 polynomial-time Floyd-Warshall algorithm.

In other words, the Floyd-Warshall 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 Floyd-Warshall 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 Bellman-Ford or Dijkstra’s shortest path algorithm on every vertex in the graph.

Yes, you can, but the main reason why we are not using Bellman-Ford 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 Floyd-Warshall 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 Floyd-Warshall 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 Bellman-Ford or Dijkstra’s shortest path algorithm is not a good choice for solving the shortest path problem concerning all pairs of vertices.

The Bellman-Ford 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 Bellman-Ford 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 Floyd-Warshall algorithm an ideal choice for us.

Applications of the Floyd Warshall Algorithm in C

Here are some applications of the Floyd warshall algorithm:

1. Performs fast computation of Pathfinder networks.
2. Helps in finding the Inversion of real matrices.
3. Helps in finding the transitive closure of directed graphs.
4. Helps in finding out if an undirected graph is bipartite or not.
5. Used in finding the shortest path in the graph.

Conclusion
In conclusion, the Floyd-Warshall 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 Bellman-Ford or Dijkstra’s shortest path algorithm, Floyd-Warshall 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 Floyd-Warshall 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 Floyd-Warshall algorithm handle graphs with negative weight cycles?
No, the Floyd-Warshall 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 Floyd-Warshall algorithm suitable for both directed and undirected graphs?
Yes, the Floyd-Warshall 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 Floyd-Warshall algorithm compare to Bellman-Ford and Dijkstra’s shortest path algorithm in terms of time complexity?
The Floyd-Warshall algorithm has a time complexity of O(V^3), where V represents the number of vertices. In contrast, Bellman-Ford has a time complexity of O(VE), and Dijkstra’s algorithm has a time complexity of O(V + ElogV). Floyd-Warshall’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 Floyd-Warshall algorithm?
The Floyd-Warshall 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 Floyd-Warshall algorithm handle weighted graphs where each edge has different weights?
Yes, the Floyd-Warshall 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.