Floyd‐Warshall Algorithm

Floyd-Warshall algorithm is a dynamic-programming formulation to solve the all-pairs shortest-paths problem on a directed graph that runs in $O(V^3)$.

The structure of a shortest path

The F-W algorithm considers the intermediate vertices of a sp, where an intermediate vertex of a simple path p={ $v_1, v_2,..,v_l$ } is any vertex of p other than $v_1$ or $v_l$, that is any vertex in the set { $v_2,..,v_l-1$ }.

Under the assumption that the vertices of G are V = {1, 2, ...,n}, let us consider a subset {1,2,...,k} of vertices for some k. For any pair of vertices i,j $\in$ V, consider all paths from i to j whose intermediate vertices are all drawn from {1,2,...,k}, and let p be a minimum-weight path from among them (path p is simple). F-W exploits a relationship between path p and shortest paths from i to j with all intermediate vertices in the set {1,2,...,k-1}. The relationship depends on whether or not k is a n intermediate vertex of path p.

• if k is not an intermediate vertex of path p, then all intermediate vertices of p are in the set {1,2,...,k-1}. Thus, a shortest path from i to j with all intermediate vertices in the set {1,2,...,k-1} is also a shortest path from i to j with all intermediate vertices in the set {1,2,...,k}.
• If k is an intermediate vertex of p, then we decompose p into i->k->j. Since we know that sub-paths of shortest paths are shortest paths, p1 = i->k is a shortest path from i to k with all intermediate vertices in the set {1,2,..,k}. Because k is not an intermediate vertex of p1, all intermediate vertices of p1 are in the set {1,2,...,k-1}, therefore, p1 is a shortest path from i to k with all intermediate vertices in the set {1,2,...,k-1}. Similarly, p2 is a shortest path from vertex k to vertex j with all intermediate vertices in the set {1,2,...,k-1}.

A recursive solution to the all-pairs shortest-path problem

Based on the above observations, we define a recursive formulation of the s-p estimates. Let $d_{ij}^{(k)}$ be the weight of a shortest path from vertex i to vertex j for which all intermediate vertices are in the set {1,2,..,k}. When k=0 a path from i to j with no intermediate vertex numbered higher than 0- has no intermediate vertices at all. Such a path has at most one edge, and hence $d_{ij}^{(0)}=w_{ij}$. Following the above, $d_{ij}^{(k)}$ can be defined recursively as

• $w_{ij}$ if k=0
• min( $d_{ij}^{(k-1)}$, $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$ ) if k $\geq$ 1

Because for any path, all intermediate vertices are in the set {1,2,...,n}, the matrix $D^{n}$ = $(d_{ij}^{(n)})$ gives the final answer:

• $(d_{ij}^{(n)})$ = $(\delta(i,j)$ for all i,j $\in$ V.

Computing the shortest-path weights bottom up

Based on the previous recurrence, we can use the following procedure to compute $(\delta(i,j)$ in order of increasing values of k.

// Floyd-Warshall algorithm
FloydWarshall(W)
    // Input: W, an n x n matrix where W[i][j] is the weight of the edge from vertex i to vertex j
    n = number of vertices in W
    D = W // Initialize D with the input weight matrix

    // Iterate through each possible intermediate vertex k
    for k = 1 to n
        // Iterate through each pair of vertices (i, j)
        for i = 1 to n
            for j = 1 to n
                // Update D[i][j] to be the minimum distance from i to j
                // either directly (D[i][j]) or through k (D[i][k] + D[k][j])
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    
    // Return the final distance matrix D which contains shortest paths between all pairs of vertices
    return D

Constructing a shortest path

One way is to compute the matrix D of shortest-path weights and then construct the predecessor matrix P form the D matrix. Given the predecessor matrix P, the PrintAllPairsShortestPath will print the vertices on a given shortest path.

Transitive Closure of a directed graph

Given a directed graph we might wish to determine whether G contains a path from i to j for all vertex pairs in V. The transitive closure of G is defined as the graph $G^$=(v, $E^$), where $E^*$ = {(i,j) : there is a path from i to j in G}.

One way to compute this is to assign a weight of 1 to each edge of E and run F-W algorithm. If there is a path from i to j, we get $d_{ij}$ < n, or max otherwise.