Floyd-Warshall Algorithm for the ASSP

In the next lessons, we’ll focus on the All Sources Shortest Path (ASSP) problem. Of course, we could solve the ASSP problem by just running Dijkstra’s algorithm once from each starting vertex. But the Floyd-Warshall algorithm, which was designed to specifically solve the ASSP problem, is a viable alternative. Its benefits are that it is very simple to implement and it runs faster than repeated Dijkstra executions on dense graphs.

The Floyd-Warshall algorithm

To explain how the Floyd-Warshall algorithm works, let’s look at a small example graph.

The Floyd-Warshall algorithm is remarkable in the sense that it is one of the few algorithms that uses the weighted adjacency matrix graph representation. Let’s assume that all edge weights are positive, so we can use a single matrix to represent the graph. The weighted adjacency matrix of our example graph is

$$A = \begin{pmatrix} 0 & 6 & 3 & 12 \\ 0 & 0 & 9 & 5 \\ 0 & 0 & 0 & 2 \\ 0 & 4 & 1 & 0 \end{pmatrix}$$

The basic idea of Floyd-Warshall is to successively transform the adjacency matrix to end up with a resulting matrix that contains the lengths of the shortest paths between each pair of nodes.

In the following, let’s write $n$ for the number of nodes $|V|$. In particular, the adjacency matrix is an $n \times n$ matrix and the nodes of the graph are numbered $0, 1, \ldots, n-1$.

The Floyd-Warshall algorithm successively computes a sequence of $n \times n$ distance matrices

$$A_0, A_1, \ldots, A_n$$

where $A_0$ can be obtained directly from the adjacency matrix and $A_n$ contains the end result.

Let’s look at the definition of these matrices $A_k$.

Distance matrices: $A_k[i, j]$ is the length of the shortest path from node $i$ to node $j$ that visits only intermediate nodes with an index less than $k$.

So, the matrix $A_k$ contains the lengths of the shortest paths between each pair of nodes, assuming that the nodes with index $\geq k$ are forbidden to visit in between. We’ll call such a path a $\mathbf{k}$-restricted shortest path.

Let’s take a deeper look at the first and last path matrix, $A_0$ and $A_n$.

The matrix $A_n$ contains the lengths of shortest paths between any pair of nodes that visit only nodes with index $< n$ in between. Since all nodes have an index $< n$, the matrix $A_n$ is our desired end result containing the lengths of the shortest paths between all pairs of nodes.

On the other hand, the matrix $A_0$ contains lengths of shortest paths between all pairs of nodes that may only visit nodes with index $< 0$ in between. Since there is no node with a negative index, the shortest paths can only be direct edges between nodes. Thus, we have

$$A_0[i, j] = \begin{cases} 0 &i = j \\ w(i, j) &(i, j) \in E \\ \infty &\text{otherwise} \end{cases}$$

Here, we follow the convention that if no shortest path between two nodes exists, then their distance is infinite. Further, the shortest path from a node to itself is the empty path of length $0$.

In particular, $A_0$ ...