Design and Analysis - Floyd Warshall Algorithm

The Floyd-Warshall algorithm is a graph algorithm that is deployed to find the shortest path between all the vertices present in a weighted graph. This algorithm is different from other shortest path algorithms; to describe it simply, this algorithm uses each vertex in the graph as a pivot to check if it provides the shortest way to travel from one point to another.

Floyd-Warshall algorithm works on both directed and undirected weighted graphs unless these graphs do not contain any negative cycles in them. By negative cycles, it is meant that the sum of all the edges in the graph must not lead to a negative number.

Since, the algorithm deals with overlapping sub-problems – the path found by the vertices acting as pivot are stored for solving the next steps – it uses the dynamic programming approach.

Floyd-Warshall algorithm is one of the methods in All-pairs shortest path algorithms and it is solved using the Adjacency Matrix representation of graphs.

Floyd-Warshall Algorithm

Consider a graph, G = {V, E} where V is the set of all vertices present in the graph and E is the set of all the edges in the graph. The graph, G, is represented in the form of an adjacency matrix, A, that contains all the weights of every edge connecting two vertices.

Algorithm

Step 1 − Construct an adjacency matrix A with all the costs of edges present in the graph. If there is no path between two vertices, mark the value as ∞.

Step 2 − Derive another adjacency matrix A₁ from A keeping the first row and first column of the original adjacency matrix intact in A₁. And for the remaining values, say A₁[i,j], if A[i,j]>A[i,k]+A[k,j] then replace A₁[i,j] with A[i,k]+A[k,j]. Otherwise, do not change the values. Here, in this step, k = 1 (first vertex acting as pivot).

Step 3 − Repeat Step 2 for all the vertices in the graph by changing the k value for every pivot vertex until the final matrix is achieved.

Step 4 − The final adjacency matrix obtained is the final solution with all the shortest paths.

Pseudocode

Floyd-Warshall(w, n){ // w: weights, n: number of vertices
   for i = 1 to n do // initiapze, D (0) = [wij]
      for j = 1 to n do{
         d[i, j] = w[i, j];
      }
      for k = 1 to n do // Compute D (k) from D (k-1)
         for i = 1 to n do
            for j = 1 to n do
               if (d[i, k] + d[k, j] < d[i, j]){
                  d[i, j] = d[i, k] + d[k, j];
               }
      return d[1..n, 1..n];
}

Example

Consider the following directed weighted graph G = {V, E}. Find the shortest paths between all the vertices of the graphs using the Floyd-Warshall algorithm.

Solution

Step 1

Construct an adjacency matrix A with all the distances as values.

$$A=egin{matrix} 0 & 5& infty & 6& infty \ infty & 0& 1& infty& 7\ 3 & infty& 0& 4& infty\ infty & infty& 2& 0& 3\ 2& infty& infty& 5& 0\ end{matrix}$$

Step 2

Considering the above adjacency matrix as the input, derive another matrix A₀ by keeping only first rows and columns intact. Take k = 1, and replace all the other values by A[i,k]+A[k,j].

$$A=egin{matrix} 0 & 5& infty & 6& infty \ infty & & & & \ 3& & & & \ infty& & & & \ 2& & & & \ end{matrix}$$

$$A_{1}=egin{matrix} 0 & 5& infty & 6& infty \ infty & 0& 1& infty& 7\ 3 & 8& 0& 4& infty\ infty & infty& 2& 0& 3\ 2& 7& infty& 5& 0\ end{matrix}$$

Step 3

Considering the above adjacency matrix as the input, derive another matrix A₀ by keeping only first rows and columns intact. Take k = 1, and replace all the other values by A[i,k]+A[k,j].

$$A_{2}=egin{matrix} & 5& & & \ infty & 0& 1& infty& 7\ & 8& & & \ & infty& & & \ & 7& & & \ end{matrix}$$

$$A_{2}=egin{matrix} 0 & 5& 6& 6& 12 \ infty & 0& 1& infty& 7\ 3 & 8& 0& 4& 15\ infty & infty& 2& 0& 3\ 2 & 7& 8& 5& 0 \ end{matrix}$$

Step 4

Considering the above adjacency matrix as the input, derive another matrix A₀ by keeping only first rows and columns intact. Take k = 1, and replace all the other values by A[i,k]+A[k,j].

$$A_{3}=egin{matrix} & & 6& & \ & & 1& & \ 3 & 8& 0& 4& 15\ & & 2& & \ & & 8& & \ end{matrix}$$

$$A_{3}=egin{matrix} 0 & 5& 6& 6& 12 \ 4 & 0& 1& 5& 7\ 3 & 8& 0& 4& 15\ 5 & 10& 2& 0& 3\ 2 & 7& 8& 5& 0 \ end{matrix}$$

Step 5

Considering the above adjacency matrix as the input, derive another matrix A₀ by keeping only first rows and columns intact. Take k = 1, and replace all the other values by A[i,k]+A[k,j].

$$A_{4}=egin{matrix} & & & 6& \ & & & 5& \ & & & 4& \ 5 & 10& 2& 0& 3\ & & & 5& \ end{matrix}$$

$$A_{4}=egin{matrix} 0 & 5& 6& 6& 9 \ 4 & 0& 1& 5& 7\ 3 & 8& 0& 4& 7\ 5 & 10& 2& 0& 3\ 2 & 7& 7& 5& 0 \ end{matrix}$$

Step 6

Considering the above adjacency matrix as the input, derive another matrix A₀ by keeping only first rows and columns intact. Take k = 1, and replace all the other values by A[i,k]+A[k,j].

$$A_{5}=egin{matrix} & & & & 9 \ & & & & 7\ & & & & 7\ & & & & 3\ 2 & 7& 7& 5& 0 \ end{matrix}$$

$$A_{5}=egin{matrix} 0 & 5& 6& 6& 9 \ 4 & 0& 1& 5& 7\ 3 & 8& 0& 4& 7\ 5 & 10& 2& 0& 3\ 2 & 7& 7& 5& 0 \ end{matrix}$$

Analysis

From the pseudocode above, the Floyd-Warshall algorithm operates using three for loops to find the shortest distance between all pairs of vertices within a graph. Therefore, the time complexity of the Floyd-Warshall algorithm is O(n³), where ‘n’ is the number of vertices in the graph. The space complexity of the algorithm is O(n²).

Example

Following is the implementation of Floyd Warshall Algorithm to find the shortest path in a graph using cost adjacency matrix -

#include<stdio.h>
int min(int,int);
void floyds(int p[10][10],int n){
   int i,j,k;
   for (k=1; k<=n; k++)
      for (i=1; i<=n; i++)
         for (j=1; j<=n; j++)
            if(i==j)
               p[i][j]=0;
            else
               p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}
int min(int a,int b){
   if(a<b)
      return(a);
   else
      return(b);
}
void main(){
   int w,n,e,i,j;
   n = 3;
   e = 3;
   int p[10][10];
   for (i=1; i<=n; i++) {
      for (j=1; j<=n; j++)
         p[i][j]=999;
   }
   p[1][2] = 10;
   p[2][3] = 15;
   p[3][1] = 12;
   printf("
 Matrix of input data:
");
   for (i=1; i<=n; i++) {
      for (j=1; j<=n; j++)
         printf("%d 	",p[i][j]);
      printf("
");
   }
   floyds(p,n);
   printf("
 Transitive closure:
");
   for (i=1; i<=n; i++) {
      for (j=1; j<=n; j++)
         printf("%d 	",p[i][j]);
      printf("
");
   }
   printf("
 The shortest paths are:
");
   for (i=1; i<=n; i++)
      for (j=1; j<=n; j++) {
         if(i!=j)
            printf("
 <%d,%d>=%d",i,j,p[i][j]);
      }
}

Matrix of input data:
999 	10 	999 	
999 	999 	15 	
12 	999 	999 	

 Transitive closure:
0 	10 	25 	
27 	0 	15 	
12 	22 	0 	

 The shortest paths are:

 <1,2>=10
 <1,3>=25
 <2,1>=27
 <2,3>=15
 <3,1>=12
 <3,2>=22

#include <iostream>
using namespace std;
void floyds(int b[][3]){
   int i, j, k;
   for (k = 0; k < 3; k++) {
      for (i = 0; i < 3; i++) {
         for (j = 0; j < 3; j++) {
            if ((b[i][k] * b[k][j] != 0) && (i != j)) {
               if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) {
                  b[i][j] = b[i][k] + b[k][j];
               }
            }
         }
      }
   }
   for (i = 0; i < 3; i++) {
      cout<<"
Minimum Cost With Respect to Node:"<<i<<endl;
      for (j = 0; j < 3; j++) {
         cout<<b[i][j]<<"	";
      }
   }
}
int main(){
   int b[3][3];
   for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
         b[i][j] = 0;
      }
   }
   b[0][1] = 10;
   b[1][2] = 15;
   b[2][0] = 12;
   floyds(b);
   return 0;
}

Minimum Cost With Respect to Node:0
10 20 30
Minimum Cost With Respect to Node:1
20 0 15
Minimum Cost With Respect to Node:2
30 15 0

pubpc class FloydWarshall {
   static void floyds(int b[][]){
      int i, j, k;
      for (k = 0; k < 3; k++) {
         for (i = 0; i < 3; i++) {
            for (j = 0; j < 3; j++) {
               if ((b[i][k] * b[k][j] != 0) && (i != j)) {
                  if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) {
                     b[i][j] = b[i][k] + b[k][j];
                  }
               }
            }
         }
      }
      for (i = 0; i < 3; i++) {
         System.out.println("
Minimum Cost With Respect to Node:" + i);
         for (j = 0; j < 3; j++) {
            System.out.println(b[i][j] + "	");
         }
      }
   }
   pubpc static void main(String args[]){
      int b[][] = new int[3][3];
      for (int i = 0; i < 3; i++) {
         for (int j = 0; j < 3; j++) {
            b[i][j] = 0;
         }
      }
      b[0][1] = 10;
      b[1][2] = 15;
      b[2][0] = 12;
      floyds(b);
   }
}

Minimum Cost With Respect to Node:0
0	
10	
25	

Minimum Cost With Respect to Node:1
27	
0	
15	
Minimum Cost With Respect to Node:2
12	
22	
0	

# Number of vertices
nV = 4
INF = 999

# Algorithm
def floyd(G):
   dist = pst(map(lambda p: pst(map(lambda q: q, p)), G))

   # Adding vertices inspanidually
   for r in range(nV):
      for p in range(nV):
         for q in range(nV):
            dist[p][q] = min(dist[p][q], dist[p][r] + dist[r][q])
   sol(dist)

# Printing the output
def sol(dist):
   for p in range(nV):
      for q in range(nV):
         if(dist[p][q] == INF):
            print("INF", end=" ")
         else:
            print(dist[p][q], end=" ")
      print(" ")

G = [[0, 5, INF, INF],
   [50, 0, 15, 5],
   [30, INF, 0, 15],
   [15, INF, 5, 0]]
floyd(G)

0  5  15 10  
20 0  10 5  
30 35 0  15  
15 20 5  0