Home

 › 

Articles

 › 

Understanding The Floyd-Warshall Algorithm, With Examples

Floyd-Warshall Algorithm

Understanding The Floyd-Warshall Algorithm, With Examples

Key Points

  • The Floyd-Warshall algorithm finds the shortest path between all vertices in a graph, making it more general than other algorithms like Dijkstra’s and Bellman-Ford.
  • It can handle negative edge weights and find the shortest paths between all vertices.
  • The algorithm uses an adjacency matrix to represent the graph and compares the distance between vertices i and j to the distance between i and k + k and j, where k is an intermediate vertex.
  • The time complexity of the algorithm is O(n^3), while the space complexity is O(n^2).
  • Real-world applications of the Floyd-Warshall algorithm include transportation networks, GPS systems, traffic management, network protocols, and pathfinding for NPC AI in video games.

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:

A graph to illustrate the Floyd-Warshall Algorithm

.

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

ABCDEF
A022INFINFINF
BINF02INFINFINF
CINFINF0226
DINFINFINF0INF2
EINFINFINFINF02
FINFINFINFINFINF0

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.

A program to illustrate the Floyd-Warshall Algorithm.

The Complexity of the Floyd-Warshall Algorithm

The time complexity of the algorithm is equal to O(n3), 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(n2), 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 n2 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.

Frequently Asked Questions

What is the Floyd-Warshall algorithm?

This is an algorithm used to find the shortest path between all vertices in a weighted graph.

How does the Floyd-Warshall algorithm work?

It works by using an adjacency matrix, of size n x n, where n is the number of vertices. The distance between vertices i and j is compared to the distance between i and k + k and j, where k is an intermediate vertex. If this distance is found to be shorter, the distance is updated in the matrix. After repeating this process, iterating over all possible intermediate vertices, we obtain an updated matrix. This gives us the shortest possible distance between all the vertices in the graph.

What is a shortest-path algorithm?

This is a type of algorithm used to find the shortest distance between vertices in a graph. There are many kinds, but the most common are Floyd-Warshall, Dijkstra’s and Bellman-Ford.

Can the Floyd-Warshall algorithm manage negative edge weights?

Yes, but it cannot handle negative cycles, where the sum of the distances along a closed path of edges is negative. In this case, Bellman-Ford is a more appropriate choice.

Why can't Floyd-Warshall be used for negative cycles in graphs?

The algorithm can’t be used here because it will infinitely keep calculating shorter paths. Bellman-Ford works here because it relies on edge relaxation, where it calculates the sum of the vertex distance and the edge weight, and compares this to the vertex distance in order to find the shortest path. As such, a negative cycle is detected if there is further possible relaxation after V-1 iterations, where V is the number of vertices.

What is the time complexity of the algorithm?

The time complexity is O(n3), where n is the number of vertices.

What is the space complexity of the algorithm?

The space complexity is O(n2), where n is the number of vertices.

What is the Floyd-Warshall algorithm used for?

The algorithm is used in many real-world situations where we want to calculate the shortest distance. These include transportation networks, flight plans, GPS systems, traffic management, network protocols and pathfinding for NPC AI in video games.

Can the algorithm deal with disconnected graphs?

Yes, the algorithm will still work for graphs with disconnected graphs. These distances will simply be represented by infinity.

To top