1. Overview

In this tutorial, we’ll discuss the Floyd-Warshall Algorithm, and then we’ll analyze its time complexity.

2. Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a popular algorithm for finding the shortest path for each vertex pair in a weighted directed graph.

In all pair shortest path problem, we need to find out all the shortest paths from each vertex to all other vertices in the graph.

Now, let’s jump into the algorithm:

Rendered by QuickLaTeX.com

We’re taking a directed weighted graph G(V, E) as an input. And first, we construct a graph matrix from the given graph. This matrix includes the edge weights in the graph.

Next, we insert \textbf{\mathsf{0}} in the diagonal positions in the matrix. The rest of the positions are filled with the respective edge weights from the input graph.

Then, we need to find the distance between two vertices. While finding the distance, we also check if there’s any intermediate vertex between two picked vertices. If there exists an intermediate vertex then we check the distance between the selected pair of vertices which goes through this intermediate vertex.

If this distance when traversing through the intermediate vertex is less then the distance between two picked vertices without going through the intermediate vertex, we update the shortest distance value in the matrix.

The number of iterations is equal to the cardinality of the vertex set. The algorithm returns the shortest distance from each vertex to another in the given graph.

3. An Example

Let’s run the Floyd-Warshall algorithm on a weighted directed graph:

At first, we construct a graph matrix from the input graph. Next, we insert \mathsf{0} to the diagonal positions in the matrix, and the rest of the positions will be filled with the edge weights from the input graph:

    \[\begin{bmatrix} 0 & \infty & -2 & \infty \\ 4 & 0 & 3 & \infty\\ \infty & \infty & 0 & 2 \\ \infty & -1 & \infty & 0 \\ \end{bmatrix} \quad\]

Now, we’re ready to start the iteration. The cardinality of the vertex set is 4. We’ll iterate the loops \mathsf{4} times.

Let’s start with the first loop. For the first loop k =1, i=1, j= 1 we’ll check if we should update the matrix:

distance[i][j] > distance[i][k] + distance[k][j] \implies distance[1][1] > distance[1][1] + distance[1][1] \implies 0 > 0 + 0 \implies {\rm FALSE}

As the loop values don’t satisfy the condition, there will be no update in the matrix.

Let’s continue, now for the values k =1, i=1, j= 2 and check again:

distance[i][j] > distance[i][k] + distance[k][j] \implies distance[1][2] > distance[1][1] + distance[1][2] \implies 0 > 0 + \infty \implies {\rm FALSE}

Thus, there will be no changes in the matrix. In this way, we’ll continue and check all pair of vertices.

Let’s fast-forward to some values that will satisfy the distance condition.

For the loop values k =1, i=2, j= 3, we’ll see that the condition is satisfied:

distance[i][j] > distance[i][k] + distance[k][j] \implies distance[2][3] > distance[2][1] + distance[1][3] \implies 3>4 + -2 \implies 3 > 2 \implies {\rm TRUE}

Because of that, we’ll compute a new distance:

distance[i][j] > distance[i][k] + distance[k][j] \implies distance[2][3] = distance[2][1] + distance[1][3] = 2

Hence, the condition satisfies for the vertex pair (2,3). At first, the distance between the vertex \mathsf{2} to \mathsf{3} was \mathsf{3}. However, we found a new shortest distance \mathsf{2} here. Because of that, we update the matrix with this new shortest path distance:

    \[\begin{bmatrix} 0 & \infty & -2 & \infty \\ 4 & 0 & 2 & \infty\\ \infty & \infty & 0 & 2 \\ \infty & -1 & \infty & 0 \\ \end{bmatrix} \quad\]

Let’s take another set of values for the three nested loops such that the loop values satisfy the distance condition given in the algorithm; k=2, i= 4, j= 1:

distance[i][j] > distance[i][k] + distance[k][j] \implies distance[4][1] > distance[4][2] + distance[2][1] \implies \infty > -1 + 4 \implies \infty>3 \implies {\rm TRUE}

As the condition satisfies, we’ll calculate a new distance calculation:

distance[i][j] > distance[i][k] + distance[k][j] \implies distance[4][1] = distance[4][2] + distance[2][1] = 3

Therefore, we update the matrix now with this new value:

    \[\begin{bmatrix} 0 & \infty & -2 & \infty \\ 4 & 0 & 2 & \infty\\ \infty & \infty & 0 & 2 \\ 3 & -1 & \infty & 0 \\ \end{bmatrix} \quad\]

Similarly, we continues and checks for different loop values. Finally, after the algorithm terminates, we’ll get the output matrix containing all pair shortest distances:

    \[\begin{bmatrix} 0 & -1 & -2 & 0 \\ 4 & 0 & 2 & 4\\ 5 & 1 & 0 & 2 \\ 3 & -1 & 1 & 0 \\ \end{bmatrix} \quad\]

4. Time Complexity Analysis

First, we inserted the edge weights into the matrix. We do this using a for loop that visits all the vertices of the graph. This can be performed in \mathcal{O}(n) time.

Next, we’ve got three nested loops, each of which goes from one to the total number of vertices in the graph. Hence, the total time complexity of this algorithm is \mathbf{\mathcal{O}(n^3)}.

5. Conclusion

To summarize, in this tutorial, we’ve discussed the Floyd-Warshall algorithm to find all pair shortest distance in a weighted directed graph.

Furthermore, we’ve also presented an example and time complexity analysis of the algorithm.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments