Floyd–Warshall algorithm

Let's assume that each node on the graph below is an airport of some city and the weight of each edge is the flight price between the two airports. To minimize the costs we need to know the most affordable prices between all pairs of airports.

Here is a basic real-life example:

You are traveling from New York to Prague and looking for an affordable flight ticket price. What will you do?

If you see an expensive direct flight, you will start looking for a connecting flight to make it more affordable. You find that a connecting flight is available via Paris, which already is cheaper. However, you decide to look further to save even more money and then end up with London being the most affordable option. This is where the Floyd-Warshall algorithm comes into use, it helps us find the most affordable prices between all pairs of airports via a connecting (intermediate) one.

Even though it doesn't happen in real life: we do not get paid for traveling from one city to another, the Floyd-Warshall algorithm can work with negatively weighted edges, meaning that the weight between the edges must not be positive.

Description of the algorithm

The main idea behind the Floyd-Warshall algorithm is to construct the shortest paths between all node pairs (or vertices).

What does it mean though?

We check whether there is a shorter path between a direct edge or via an intermediate node.

On the left picture, there is a direct edge example. On the right one, we have a third node $k$, via which we get a shorter distance – profit!

Like that, we go through all the intermediary nodes and gradually build up the shortest path information until all possible paths are considered.

Let us break down the algorithm into logical steps and take a closer look:

• Step 1: Initialize our graph of nodes. We either set the length of the shortest path between the two nodes by the weight between them, if given, or we set it to $\infty$. Furthermore, the distance from a node to itself is set to zero, as there is no need for a node to travel to reach itself.
• Step 2: Intermediate nodes. We take the first node in the graph as an intermediate and check whether it can be used to shorten the current path by updating it if necessary.
• Step 3: Update rule. Let us consider the example above. If the distance via an intermediary is shorter than the initial distance, then we update it. If not, then the weight stays the same. Mathematically it looks like this:

$M^k(i, j) = min\{A^{k-1}(i, j), A^{k-1}(i, k) + A^{k-1}(k, j)\}$,

where $M$ is the Matrix, $k$ is the intermediate, $i$ is the starting node and $j$ is the destination node.

We repeat step 2 by setting the next node as the next intermediate and step 3 by comparing the lengths between the current intermediate and the lengths from the previous intermediate. These steps are repeated up until the last node in the graph.

Initialization logic

Let us look at the very first simple graph consisting of 2 nodes to understand how it is done.

Our first row features the node i, which points to j

Each row of the table indicates the starting node, whereas the column is the destination node.

The diagonal elements in the table are zeroes because this is the distance from the same node to itself.

The other elements of the table are replaced by the weights of the distances provided by the graph.

Example

To get a better understanding of the algorithm, let us look at an example with the following graph.

Just like we did before: zeroes go into the diagonal of the table, and other elements are either replaced by the weights provided by the graph or replaced by $\infty$, because these pairs of nodes do not connect with each other. As a result, we have the following filled-out table:

For our first intermediate node (k = 0) we are going to take our matrix M as a basis and create a new matrix by updating the distances, if needed. We don't have to update the first row nor the first column because our current intermediate isn't going to have any impact on the update. Therefore, we start with $[B,C]$ (because $[B,B]$ is a zero in our table).

Let us make a path via the intermediate:

$(i,j) = (i, k) + (k, j)$ in which case $[B, C] = [B, A][A, C]$.

We recall our update rule and check whether our basis matrix M has a greater distance than the sum of $[B,A]$ and $[A,C]$.

The result is: $3 < 7 + \infin$, therefore we do not update the element's value.

Let us check the next element and decide if it needs to be updated:

This time we check $[B, D] = [B, A][A, D]$, whether the sum is going to be less than [B, D]. In this case, it actually is, $11 < \infin$, which means that we update the value in our table!

Lastly, let us take a look at our third example:

We get to our $[D, B]$ element, which is the sum of $[D, A][A,B]$. What should we do in this case? Should we update or not?

You are absolutely right: $\infin > 2 + 5$, which means that we update our $[D, B]$ element in the table.

We continue up to the last element in the table and then move to the next intermediate node until we are through all of them.

Our final table $M^{k=D}$ represents the shortest paths between all pairs of nodes, which means that our algorithm has finished its job.

Pseudocode

for k in range(V):                                    # Intermediate node
    for i in range(V):                                # Source node
        for j in range(V):                            # Destination node
            M[i][j] = min(M[i][j], M[i][k] + M[k][j]) # Update rule

These nested for loops look pretty straightforward: from every vertex $i$ we search a path to vertex $j$ and then compare, whether the result via intermediate $k$ is going to be shorter. As we cycle through all the intermediate nodes, we compare them with all of the vertex pairs.

Complexity and other features

Every algorithm has its advantages and disadvantages. It is worth mentioning that the Floyd-Warshall algorithm can handle negative edges, however, it cannot be applied to negative cycles. It is when the sum of the edges' weights is a negative value.

We saw the algorithm's 3 nested for loops, which makes the time complexity be $O(n^3)$.

The Floyd-Warshall algorithm is based on the principle of dynamic programming. It is when a problem is broken down into sub-problems and solved iteratively. It is also a non-greedy algorithm, which means that it takes all possible routes while a greedy algorithm does not reconsider its choices for the shortest paths.

On top of that, both directed and undirected graphs can be thrown at the algorithm to handle. The last one means that the edges do not have a direction.

If we want to calculate the distance between all node pairs and not just one, then this dynamic algorithm is a great choice for handling this sort of problem. On the other hand, with a sparse graph without any negative edges, Dijkstra's algorithm is a better choice as lower time complexity means it requires less time to run through.

Conclusion

We took a look at the Floyd-Warshall algorithm and here's what we learned from this topic:

• The initial matrix of the group serves as the basis and then the intermediate nodes update the paths if necessary.
• The basic algorithm can be implemented rather easily, it features 3 for loops and an if condition.
• Floyd-Warshall algorithm is especially efficient with dense graphs with nodes consisting of negative edges.
• Floyd-Warshall is a dynamic programming-based algorithm.
• Flow-Warshall is a non-greedy algorithm.
• The time complexity of the Floyd-Warshall algorithm is $O(n^3)$.

Now we can move forward with solving tasks assigned to this topic.