Floyd Warshall Algorithm

This article will discuss the Floyd warshall algorithm, the working of the Floyd warshall algorithm, implementation of the Floyd warshall algorithm in C++, time complexity analysis of the Floyd warshall algorithm, and last we will also look at some applications of the Floyd warshall algorithm.

Floyd Warshall Algorithm

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

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

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
The Floyd-Warshall algorithm is one of the shortest path-finding algorithms for graphs and you can apply its properties to solve many real-life problems.