Understanding The Floyd-Warshall Algorithm, With Examples

Finding the shortest distance between paths on a graph is a very common problem in programming. From computer and social network analysis to GPS systems, transport networks, and even pathfinding in video games, shortest-path algorithms have many applications. Not all of them are suitable for each use case, however. Picking the correct algorithm to use is crucial to solve the problem successfully. In this article, we’re going to describe the Floyd-Warshall algorithm, what it’s used for, and how to implement it easily.

What is Floyd-Warshall, and What is it Used For?

The Floyd-Warshall algorithm is of a type known as a shortest-path algorithm. This is because it’s used to find the shortest path between the vertices in a graph. We can use Dijkstra’s algorithm to accomplish a similar result, but there are some differences. Dijkstra’s can only work with graphs where the edge weights are positive and is used to find the shortest path between one vertex and all other vertices. Another choice is the Bellman-Ford algorithm, which can be used for negative edge weights, as well as negative cycles (where the sum of weights is negative). Floyd-Warshall, however, is used more generally, to find the shortest paths between all vertices. This is something the other algorithms cannot do. As such, it has many uses, such as in network protocols, computational science, transport networks, and traffic management.

How to Use the Floyd-Warshall Algorithm

The main idea behind the Floyd-WArshall algorithm is to use an adjacency matrix to represent the graph. This is done by listing the vertices as columns and rows and then filling in the weights between these vertices. If there is no connection between two vertices, we list this distance as infinity. For the cells representing the same vertices, we input 0. To illustrate, consider this graph:

The layout can be represented with the following n x n matrix or square matrix:

The Floyd-Warshall algorithm then considers the intermediate vertices between one vertex and the other in question. If this distance, known as k, is shorter, then the matrix is updated. This continues, using all vertices as potential intermediate points. We can represent this process with the following equation:

(A[i][k] + A[k][j]) if (A[i][j] > A[i][k] + A[k][j])

Where A is the matrix weight, i is the source vertex, j is the end vertex and k is the intermediate vertex. We update the matrix with the result of the first two terms if the distance is smaller.

Let’s illustrate this with our example from earlier. Using Python, we can input the algorithm as follows:

def floyd_warshall(graph):
    n = len(graph)
    distance = [row[:] for row in graph]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if distance[i][k] + distance[k][j] < distance[i][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]

    return distance


inf = float('inf')

graph = [
    [0, 2, 2, inf, inf, inf],
    [inf, 0, 2, inf, inf, inf],
    [inf, inf, 0, 2, 2, 6],
    [inf, inf, inf, 0, inf, 2],
    [inf, inf, inf, inf, 0, 2],
    [inf, inf, inf, inf, inf, 0]
]

result = floyd_warshall(graph)

for row in result:
    print(row)

Explanation of code

We define the Floyd-Warshall algorithm as a function of “graph”, where “n” is the number of rows or columns in the graph, which is equivalent to the number of vertices. A separate matrix is then created, with the “distance” variable initialized with the same values.

We then start our for loop, which has two nested loops within. These are used to iterate over the i, j, and k vertices. As mentioned before, if the distance between i and k + k and j is shorter than the distance between i and j, the distance is updated in the second matrix. The algorithm repeats the process recursively until all distances have been calculated.

The last step is to define the “inf” variable to represent infinity and input our graph data. The “result” variable is assigned to the graph, and a for loop is used to print all the distances. We can see the updated matrix in the image below.

The Complexity of the Floyd-Warshall Algorithm

The time complexity of the algorithm is equal to O(n³), where n is the number of vertices. This is because there are 3 vertices and 3 for loops used. We iterate n times to the power of 3, hence the complexity.

The space complexity is equal to O(n²), where n is the number of vertices. Since we require additional space to store the adjacency matrix, the space required scales quadratically. This is because the size of the matrix is n x n, giving us n² overall.

Wrapping Up

While it’s not suitable for graphs with negative cycles, Floyd-Warshall can handle negative edge weights in general. As well as this, it provides us with the shortest path between all vertices, so has advantages over both Bellman-Ford and Dijkstra’s. Floyd-Warshall finds many uses, from transport networks and traffic management to network protocols and navigation systems. By creating a matrix representation of our graph, we can quickly determine the shortest paths between all vertices. Since each has its own pros and cons, understanding how different shortest-path algorithms work is very useful in your programming efforts.

The image featured at the top of this post is ©FOTOGRIN/Shutterstock.com.