How does the Floyd-Warshall algorithm work?

The Floyd-Warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but no negative cycles). It is a classic example of dynamic programming.

It works by incrementally improving an approximation to the shortest path distances. To see why it works, consider any shortest path from point i to j: such a path can either go directly from i to j (in the edge case that i = j, this is a path of length 0), or it can go through some intermediate points. The key insight is that if the path goes through some intermediate points, then the sub-path from i to the first intermediate point, and the sub-path from the last intermediate point to j, must themselves be shortest paths. In other words, we can build up shortest paths from shortest sub-paths.

Now let’s express this in more formal terms:

- First, initialize your distance matrix with your adjacency matrix. Let’s call this matrix D[0]. In D[0][i][j], you store the distance from i to j (if there is an edge), or infinity (if there is no edge). The diagonal should be all 0, because the distance from any node to itself is 0.

- Then, iterate k from 1 to n, where n is the number of vertices. On each iteration, you construct a new matrix D[k] from D[k-1].

- To calculate the entries of D[k], we use the following rule: D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j]). In other words, either the shortest path from i to j does not go through k, or it is cheaper to go from i to k and then from k to j.

Here’s why this works: when we’re filling in the D[k] matrix, we’re considering paths that only go through nodes 1 to k. At each step, we maintain the property that D[k][i][j] is the length of the shortest path from i to j that only goes through nodes 1 to k. By considering whether or not we go through k, we ensure that we consider all possible paths. A key insight is that all shortest paths with this property can be built by taking a shortest path with the same property that ends at k, and appending an edge from k to j.

The algorithm has the formula:
D^(k)_ij = min(D^{(k − 1)}_ij, D^{(k − 1)}_ik + D^{(k − 1)}_kj)

Here, D^(k)_ij is the length of the shortest possible path from node i to node j over all paths that only use some subset of nodes 1, 2, ..., k as intermediate nodes.

By systematically applying this formula for k = 1 to n, and i, j = 1 to n at each step, we can compute the shortest paths between all pairs of nodes. The final result will be D⁽ⁿ⁾. This will yield the shortest-path distances between all pairs of nodes, considering paths that use any subset of nodes as intermediate nodes.

The time complexity of this algorithm is O(n³), as it involves three nested loops over the number of vertices.

Here is a simple pseudo-code representation for the Floyd-Warshall algorithm:

Algorithm FloydWarshall(weights[][], n):
    initialize D as weights[][]
    for k from 1 to n
        let D_in_k_minus_1 = D
        for each i from 1 to n
            for each j from 1 to n
                D[i][j] = min(D_in_k_minus_1[i][j] , D_in_k_minus_1[i][k] + D_in_k_minus_1[k][j])
    return D         

At the end of this algorithm, D[i][j] holds the shortest distance from node i to node j.