Floyd Warshall Algorithm

In this blog I’ll be talking about the Floyd Warshall algorithm which is used to solve the problem of finding the shortest path between every pair of vertices in a weighted graph. A graph is a data structure consisting of vertices connected to each other. Weighted graph means that all the edges have a number on them.

This algorithms works for both directed and undirected graphs but doesn’t work for graphs with negative cycles.

It differs from Bellman-Ford and Dijkstra’s algorithm in that it calculates minimum difference between all the vertices in the graph whereas both of these algorithms only calculate shortest path from a single vertex.

This algorithm is also an example of Dynamic Programming. Why? Because it also divides a big problem into smaller subproblems and then combines the answers to those to find the answer to the initial big problem.

Pseudo-Code for the Floyd Warshall Algorithm:

Okay, so this is the pseudo-code for the Floyd Warshall Algorithm. Now I’ll explain step by step how this algorithm works with an example:

The given graph

1. So first we start by creating a matrix (let’s say A⁰) and n here is the number of vertices in the graph. i and j represent pairs of vertices of a graph. k represents intermediate vertices between i and j. The dimension of the matrix is n*n. Now each cell of this matrix has the value which is the distance between the two vertices. If the vertices aren’t connected directly, then the value will be infinity. For self, input the value as 0. So the diagonal of the matrix will be 0.

2. Now an A¹ matrix will be created using the A⁰ matrix. The values for the paths for vertex 1 will remain the same and the diagonal values will be 0. For the rest, we will check if there is a path through vertex 1 which is shorter. We will select the lesser of both. A⁰[2,3] = 2 which is lesser than if we calculate using 1, which becomes A⁰[2,1] + A⁰[1,3] = 8 + ∞ = ∞ . So we keep 2. Same is calculated for all other pair of vertices keeping 1 as an intermediate vertex. Which basically yields us a formula A[i][j] = min (A[i,j], A[i,k] + A[k,j]). A¹ matrix after these calculations:

3. Now A² matrix is created using A¹ matrix using the same formula (keeping the connections of 2 the same and the diagonal values 0).

4. Similarly A³ and A⁴ are calculated. Since the graph has 4 vertices, A⁴ matrix gives the shortest path between all pairs of vertices.

Time and Space Complexity:

The graph has n vertices. Since there are 3 nested loops, each having a complexity of O(n), we get the total time complexity as O(n³). The space complexity of this algorithm is O(n³).

Advantages of Floyd Warshall algorithm:

1. A single execution of the algorithm gives us the shortest path between all the vertices.
2. This algorithm can also be used to find transitive closure of a relation R.

Disadvantages of Floyd Warshall algorithm:

1. It doesn’t work when there are negative cycles in the graph.
2. It does not give the details of the paths.

Thank You.