Floyd-Warshall Algorithm

Floyd-Warshall Algorithm is an algorithm for locating the shortest path between all the pairs of vertices during a weighted graph. This algorithm works for both the directed and undirected weighted graphs. But it doesn't work for the graphs with negative cycles (where the sum of the sides during a cycle is negative).

Floyd-Warshall algorithm is additionally called as Floyd's algorithm, Roy-Floyd algorithm, Roy-Warshall algorithm, or WFI algorithm.

This algorithm follows the dynamic programming approach to seek out the shortest paths.


How to Floyd Warshall Algorithm Works?

Let’s the given be a Graph

Initial Graph

Follow the steps below to seek out the shortest path between all the pairs of vertices.

Step 1: Create a matrix A0 of dimension n*n where n is that the number of vertices. The row and therefore the column are indexed as i and j respectively. i and j are the vertices of the graph. 

Each cell A[i][j] is crammed with the space from the ith vertex to the jth vertex. If there's no path from ith vertex to jth vertex, the cell is left as infinity.

Fill each cell with the distance between ith  and jth vertex



Step 2:  Now, create a matrix A1 using matrix A0. the weather within the first column and therefore the first row is left as they’re. The remaining cells are filled within the following way.

Let k be the intermediate vertex within the shortest path from source to destination. during this step, k is that the first vertex. A[i][j] is crammed with (A[i][k] + A[k][j])  if (A[i][j] > A[i][k] + A[k][j]).

That is, if the direct distance from the source to the destination is bigger than the trail through the vertex k, then the cell is crammed with A[i][k] + A[k][j].

In this step, k is vertex 1. We calculate the space from source vertex to destination vertex through this vertex k.

Calculate the distance from the source vertex to the destination vertex through this vertex k


For example: For A1[2, 4], the direct distance from vertex 2 to 4 is 4 and therefore the sum of the space from vertex 2 to 4 through vertex (ie. from vertex 2 to 1 and from vertex 1 to 4) is 7. Since 4 < 7, A0[2, 4] is crammed with 4.

Step 3: Similarly, A2 is made using A1. the weather within the second column and therefore the second row are left as they’re.
In this step, k is that the second vertex (i.e. vertex 2). The remaining steps are an equivalent as in step 2.

 Calculate the distance from the source vertex to the destination vertex through this vertex 2


Step 4: Similarly, A3 and A4 is additionally created

Calculate the distance from the source vertex to the destination vertex through this vertex 3




Calculate the distance from the source vertex to the destination vertex through this vertex 4

Step 5: A4 gives the shortest path between each pair of vertices.


Floyd-Warshall Algorithm

n = no of vertices
A = matrix of dimension n*n
for k = 1 to n
    for i = 1 to n
        for j = 1 to n
            Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
return A

Python, Java and C/C++ Example.

Code in Python:
# Floyd Warshall Algorithm in python
# The number of vertices
nV = 4
INF = 999
# Algorithm implementation
def floyd_warshall(G):
    distance = list(map(lambda i: list(map(lambda j: j, i)), G))
 
    # Adding vertices individually
    for k in range(nV):
        for i in range(nV):
            for j in range(nV):
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
    print_solution(distance)
 
# Printing the solution
def print_solution(distance):
    for i in range(nV):
        for j in range(nV):
            if(distance[i][j] == INF):
                print("INF", end=" ")
            else:
                print(distance[i][j], end="  ")
        print(" ")
 
 
G = [[0, 3, INF, 5],
         [2, 0, INF, 4],
         [INF, 1, 0, INF],
         [INF, INF, 2, 0]]
floyd_warshall(G)

Code in Java:
// Floyd Warshall Algorithm in Java
 
class FloydWarshall {
  final static int INF = 9999, nV = 4;
 
  // Implementing floyd warshall algorithm
  void floydWarshall(int graph[][]) {
    int matrix[][] = new int[nV][nV];
    int i, j, k;
 
    for (i = 0; i < nV; i++)
      for (j = 0; j < nV; j++)
        matrix[i][j] = graph[i][j];
 
    // Adding vertices individually
    for (k = 0; k < nV; k++) {
      for (i = 0; i < nV; i++) {
        for (j = 0; j < nV; 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[][]) {
    for (int i = 0; i < nV; ++i) {
      for (int j = 0; j < nV; ++j) {
        if (matrix[i][j] == INF)
          System.out.print("INF ");
        else
          System.out.print(matrix[i][j] + "  ");
      }
      System.out.println();
    }
  }
 
  public static void main(String[] args) {
    int graph[][] = { { 0, 3, INF, 5 }, { 2, 0, INF, 4 }, { INF, 1, 0, INF }, { INF, INF, 2, 0 } };
    FloydWarshall a = new FloydWarshall();
    a.floydWarshall(graph);
  }
}

Code in C:
// Floyd-Warshall Algorithm in C
 
#include <stdio.h>
// defining the number of vertices
#define nV 4
#define INF 999
 
void printMatrix(int matrix[][nV]);
// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
  int matrix[nV][nV], i, j, k;
 
  for (i = 0; i < nV; i++)
    for (j = 0; j < nV; j++)
      matrix[i][j] = graph[i][j];
 
  // Adding vertices individually
  for (k = 0; k < nV; k++) {
    for (i = 0; i < nV; i++) {
      for (j = 0; j < nV; 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[][nV]) {
  for (int i = 0; i < nV; i++) {
    for (int j = 0; j < nV; j++) {
      if (matrix[i][j] == INF)
        printf("%4s", "INF");
      else
        printf("%4d", matrix[i][j]);
    }
    printf("\n");
  }
}
 
int main() {
  int graph[nV][nV] = {{0, 3, INF, 5},
             {2, 0, INF, 4},
             {INF, 1, 0, INF},
             {INF, INF, 2, 0}};
  floydWarshall(graph);
}

Code in C++:
// Floyd-Warshall Algorithm in C++
 
#include <iostream>
using namespace std;
 
// defining the number of vertices
#define nV 4
#define INF 999
 
void printMatrix(int matrix[][nV]);
 
// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
  int matrix[nV][nV], i, j, k;
 
  for (i = 0; i < nV; i++)
    for (j = 0; j < nV; j++)
      matrix[i][j] = graph[i][j];
 
  // Adding vertices individually
  for (k = 0; k < nV; k++) {
    for (i = 0; i < nV; i++) {
      for (j = 0; j < nV; 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[][nV]) {
  for (int i = 0; i < nV; i++) {
    for (int j = 0; j < nV; j++) {
      if (matrix[i][j] == INF)
        printf("%4s", "INF");
      else
        printf("%4d", matrix[i][j]);
    }
    printf("\n");
  }
}
 
int main() {
  int graph[nV][nV] = {{0, 3, INF, 5},
             {2, 0, INF, 4},
             {INF, 1, 0, INF},
             {INF, INF, 2, 0}};
  floydWarshall(graph);
}

Floyd Warshall Algorithm Complexity:

Time Complexity:

There are three loops. Each loop has constant complexities. So, the time complexity of the Floyd-Warshall algorithm is O(n3).

Space Complexity:

The space complexity of the Floyd-Warshall algorithm is O(n2).

Floyd Warshall Algorithm Application.

1. To find the shortest path may be a directed graph
2. To find the transitive closure of directed graphs
3. To find the Inversion of real matrices
4. For testing whether an undirected graph is bipartite

Comments

Post a Comment

Popular posts from this blog

Brent's Algorithm

Image
Brent's Cycle detection Algorithm Given a linked list, check if the linked list has loop or not. Below diagram shows a linked list with a loop.   Brent’s cycle detection algorithm is analogous to Floyd's algorithm because it also uses two pointer technique. But there's some difference in their approaches. Here we make one pointer stationary till every iteration and teleport it to other pointer at every power of two. the beginning of the cycle is decided by the littlest power of two at which they meet. This improves upon the constant factor of Floyd’s algorithm by reducing the amount of calls. Move fast pointer (or second_pointer) in powers of two until we discover a loop. After every power, we reset slow pointer (or first_pointer) to previous value of second pointer. Reset length to 0 after every every power. The condition for loop testing is first_pointer and second_pointer become same. And loop isn't present if second_pointer becomes NULL. The condition for loop test...
Read more