All About Floyd-Warshall Algorithm

All About Floyd-Warshall Algorithm

6 mins read4.9K Views Comment
Updated on Oct 28, 2022 13:56 IST

Floyd Warshall is a dynamic programming algorithm used to solve all pair shortest path problems. Dynamic Programming is an approach used in data structure and algorithms for solving problems efficiently, this approach is known for providing the most optimized result. Dynamic programming solves a class of problems using overlapping subproblems, memorization, and optimal substructure property.
Author: Kanika Joshi

2022_10_MicrosoftTeams-image-74.jpg

Floyd Warshall algorithm is the shortest path algorithm, similar to Dijkstra’s algorithm and Bellman ford’s algorithm. The only difference is Dijkstra’s and Bellman Ford’s algorithms are single source shortest path algorithms, whereas Floyd Warshall is all pair shortest path algorithm, it can compute the shortest path between every pair of vertices in the graph. 

In this article, we are going to discuss Floyd Warshall algorithm, the working of Floyd warshall algorithm, its complexity, and its applications. 

Table of Contents

What is Floyd Warshall Algorithm?

Floyd Warshall is a dynamic programming-based algorithm so it breaks the problem into smaller subproblems and then solves each unitary subproblem after that it combines the result to solve the bigger problem while storing the result of each subproblem for future reference. 

It is also known as Floyd’s algorithm, Roy-Floyd algorithm, Roy-Warshall algorithm, and WF algorithm. 

Floyd Warshall is all pair shortest path algorithm used to find the shortest path or shortest distance between every pair of vertices in the given graph. The algorithm is applicable on both directed and undirected graphs, but it fails with the graph having negative cycles; a negative cycle means the sum of the edges in a cycle is negative. 

Explore free data structure and algorithms courses

Algorithm

  1. Make a matrix for the given input graph. 
  2. Create another solution matrix same as the input graph matrix.
  3. Update the solution matrix while considering all vertex as an intermediate vertex. 
  4. Choose each vertex one by one and update all the shortest paths that includes the selected vertex as an intermediate vertex in the shortest path.
  5. If a vertex k is selected as an intermediate vertex, then {0, 1, 2 ….. k-1} will be considered as an intermediate vertex automatically. 
  6. For every pair of vertex (i, j) i.e. source and destination respectively, two cases are possible:
    1. k is not an intermediate vertex between i and j. The value of the distance between i and j  dist[i][j] will remain the same.
    2. if k is an intermediate vertex between i and j. The value of  dist[i][j] will become  dist[i][k] +  dist[k][j] if  dist[i][j] >  dist[i][k] +  dist[k][j]

Explore Free Online Courses with Certificates

Psuedo Code

n = no of vertices

D = matrix of dimension n*n

for k = 1 to n

    for i = 1 to n

        for j = 1 to n

            Dk[i, j] = min (Dk-1[i, j], Dk-1[i, k] + Dk-1[k, j])

return D

Learn how to write good pseudocode

Working of Floyd Warshall Algorithm

Let’s understand the working of Floyd’s Warshall algorithm with an example:

Floyd Warshall algorithm working

Make the distance matrix or graph matrix. Insert the distance value and if the distance is unknown fill that with ∞. 

D0 = 

A B C D
A 0 6 5
B 3 0 2
C 4 0
D 7 0

Now calculating the Distance of every pair Via A. 

DA = 

A B C D
A 0 6 5
B 3
C
D

Applying Floyd’s Warshall algorithm, 

D0 [B, C] = D0 [B, A] + D0 [A, C]

∞ > 3 + 5 

∞ > 8….. updating the distance 

D0 [B, C] = 8

D0 [B, D] = D0 [B, A] + D0 [A, D]

2 > 3 + ∞ 

2 > ∞….. No changes

D0 [B, D] = 2

D0 [C, B] = 8

D0 [C, D] = D0 [C, A] + D0 [A, D]

∞ > ∞ + ∞ 

∞ > ∞….. No changes

D0 [C, D] = ∞

D0 [D, B] = D0 [D, A] + D0 [A, B]

∞ > ∞ + ∞ 

∞ > ∞….. No changes

D0 [D, B] = ∞

D0[D, C] = 7

Similarly for all other vertices, the resulting matrix will look like

DA = 

A B C D
A 0 6 5
B 3 0 8 2
C 4 0
D 7 0

Now calculating the Distance of every pair Via B 

DB = 

A B C D
A 6
B 3 0 8 2
C 4
D

After applying Floyd’s Warshall formula, we get

D0 [A, C] =  D0 [A, B] + D0 [B, C]

5 > 6 + ∞…… False, No changes required.

D0 [A, C] = 5

D0 [A, D] =  D0 [A, B] + D0 [B, D]

∞ > 6 + 2…… Update the value.

D0 [A, D] = 8

D0 [C, A] =  D0 [C, B] + D0 [B, C]

∞ > 4 + 3…… Update the value.

D0 [C, A] = 7

D0 [C, D] =  D0 [C, B] + D0 [B, D]

∞ > 4 + 2…… Update the value.

D0 [C, D] = 6

D0 [D, A] =  D0 [D, B] + D0 [B, A]

∞ > ∞  + 3…… No changes are required.

D0 [C, A] = ∞

D0 [D, C] =  D0 [D, B] + D0 [B, C]

∞ > ∞ + 2…… No changes required.

D0 [C, D] = ∞

DB = 

A B C D
A 0 6 5 8
B 3 0 8 2
C 7 4 0 6
D 7 0

Now, calculating distance of each path via C.

DC = 

A B C D
A 5
B 8
C 7 4 0 6
D 7

After applying Floyd’s Warshall formula, we get

D0 [A, B] =  D0 [A, C] + D0 [C, B]

6 > 5 + 4…… False, No changes required.

D0 [A, B] = 6

D0 [A, D] =  D0 [A, C] + D0 [C, D]

8 > 5 + 6…… False, No changes required..

D0 [A, D] = 8

D0 [B, A] =  D0 [B, C] + D0 [C, A]

3 > 0 + 7…… False, No changes required.

D0 [B, A] = 3

D0 [B, D] =  D0 [B, C] + D0 [C, D]

2 > ∞ + 6…… False, No changes required.

D0 [B, D] = 2

D0 [D, A] =  D0 [D, C] + D0 [C, A]

∞ > 7  + 7…… Update the value.

D0 [D, A] = 14

D0 [D, B] =  D0 [D, C] + D0 [C, B]

∞ > 7 + 4…… Update the value.

D0 [D, B] = 11

DC = 

A B C D
A 0 6 5 8
B 3 0 8 2
C 7 4 0 6
D 14 11 7 0

Similarly, if we calculate the shortest distance Via D, No changes will be required. 

Hence, the shortest path matrix using Floyd’s Warshall algorithm is as follows:

A B C D
A 0 6 5 8
B 3 0 8 2
C 7 4 0 6
D 14 11 7 0
Data Structures and Algorithms in Python – All You Need to Know
Data Structures and Algorithms in Python – All You Need to Know
Python is a high-level, object-oriented programming language. It is a general-purpose language that is used in a variety of applications such as software testing, web development, data science, machine learning,...read more
Understanding Dijkstra’s Algorithm
Understanding Dijkstra’s Algorithm
Dijkstra’s algorithm or Dijkstra’s shortest path algorithm or single source shortest path algorithm is used in identifying the shortest path from starting node to a destination node in a weighted...read more
All About Kruskal’s Algorithm
All About Kruskal’s Algorithm
Kruskal’s algorithm is based on a greedy approach, whose goal is to find the shortest path in a graph with a minimum cost.

Complexity

Following are the complexities in the algorithm:

  • Time Complexity: There are three for loops in the pseudo-code of the algorithm, so the time complexity will be O (n^3).
  • Space Complexity: The space complexity of Floyd’s Warshall algorithm is O (n^2).

Application

  • In networking devices
  • In Routing data packets
  • Calculate the inversion of the real matrix
  • Calculating transitive closure of directed graphs
  • To check whether an undirected graph is bipartite
  • To find the shortest path in a directed graph

_______________

Recently completed any professional course/certification from the market? Tell us what you liked or disliked in the course for more curated content.

Click here to submit its review with Shiksha Online

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio