All About Floyd-Warshall Algorithm
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
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.
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Algorithm
- Make a matrix for the given input graph.
- Create another solution matrix same as the input graph matrix.
- Update the solution matrix while considering all vertex as an intermediate vertex.
- 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.
- If a vertex k is selected as an intermediate vertex, then {0, 1, 2 ….. k-1} will be considered as an intermediate vertex automatically.
- For every pair of vertex (i, j) i.e. source and destination respectively, two cases are possible:
- 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.
- 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:
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 |
Read Later
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
Top Picks & New Arrivals
