Floyd Warshall Algorithm

4 min readDec 25, 2020

Graph:

A Graph is a non-linear data structure, which consists of nodes (also called vertices) and edges for joining the vertices.

We use graphs for finding shortest possible route to some place, to get suggestions of nearest restaurants. You also get some friend suggestions on various social media platforms like Facebook which also uses graph data structure for implementing such features.

A path with minimum distance between two vertices is known as “Shortest Path”.

There are many algorithms for finding shortest paths in weighted graphs. They are:

1. Dijkstra’s Algorithm

2. Bellman Ford Algorithm

3. Floyd Warshall Algorithm

Let’s see the Floyd Warshall Algorithm and its working.

Floyd Warshall Algorithm:

Floyd Warshall Algorithm (also known as Floyd’s Algorithm) is an algorithm used to find all pairs shortest path (APSP) of vertices in a edge-weighted graph. But, it does not work with graphs which has negative cycles (where the sum of edges in the graph comes negative). This algorithm follows the dynamic programming approach which means with every step there is need to make a decision.

How the algorithm works?

Let the graph given be:

To find the shortest path between vertices, we need to create a adjacency matrix A0 of n x n dimension.

The row of matrix is indexed as ‘i’ and column is indexed as ‘j’. Here i and j are the vertices. The matrix is filled by entering the distance between i and j.
If there is no path between i and j, so it is kept as infinity.
If the vertex is not in loop, then it is kept as 0 (zero), otherwise 1. Therefore, here the diagonal of A0 matrix taken is zero.

A0 Matrix would be like:

Now, A1 matrix is needed to be created by using A0 matrix. Here, we will consider a intermediate vertex which is vertex 1. So we will get a better shortest path going via vertex 1.

As we considered vertex 1, therefore, all the paths that belong to vertex 1 remain unchanged. And no vertex is in loop, therefore, the diagonal will be zero.

To get the remaining values of the matrix, we’ll check if there is shorter path via vertex 1 or not. We select the minimum of both.

A0[2][3] = 2 < A0[2,1] + A0[1,3] = 8 + ∞ = ∞

A0[2][4] = ∞ > A0[2,1] + A0[1,4] = 8 + 7 = 15

So, in the same way, all the values are calculated.

We get a generalized formula — A[i][j] = min (A[i,j], A[i,k] + A[k,j])

where k is the intermediate vertex.

The final A1 vertex we get is:

Similarly, A2 is created using the A1 matrix by considering 2 as intermediate vertex. Here, second row and second column remain unchanged. And the diagonal remain zero.

The A2 matrix which we get is -

Similarly, we will find A3 and A4 matrices taking vertices 3 and 4 as intermediate vertex, respectively.

A4 gives the shortest path between all the vertices.

Code:

How to write the algorithm? So, implementing the above logic, for n x n dimension matrix (n rows and n columns) 2 for loops are needed and one for loop for number of vertices considering as intermediate vertex.

Implementation of Floyd Warshall Algorithm

Complexity:

Time Complexity:

We need 3 loops to implement the algorithm. Each loop has constant complexity. Therefore, the time complexity is O(n³). Here, n is the total no. of vertices in a graph.

Space Complexity:

The space complexity of Floyd Warshall Algorithm is O(n²).

Applications:

Some real-life applications where Floyd-Warshall Algorithm can be used are:

1. Google Maps: Floyd Warshall algorithm can be used to find a shortest path from one location to another in minimum time. Here, location act as vertices and time needed will be the weight on the particular edge.

2. Social Network Analysis : Floyd Warshall Algorithm can be used to connect people with strong bonds. As people with strong bonds usually tend to communicate more. The shortest path between people, which will be considered as nodes, can be calculated.

3. We can also use Floyd-Warshall algorithm to find a maximum bandwidth path in network systems.

4. Besides all, we can compare two graphs to find the similarities between them.