Floyd-Warshall

Why it exists

Sometimes the distances between all pairs of vertices are needed: a table of distances between cities, the routing tables of a small network, the answer to "can $i$ reach $j$?" for every pair. One could run Dijkstra or Bellman-Ford from every vertex; Floyd-Warshall instead does it with three nested loops and a matrix, in $\Theta(V^3)$ time. It is simple, handles negative edges, detects negative cycles, and is the standard example of a dynamic program over the set of allowed intermediate vertices.

Prerequisites

You need the dynamic programming recipe of state, recurrence and filling order (dynamic programming).

Precise definitions

All-pairs shortest paths. For a weighted directed graph on vertices $0, \ldots, V - 1$, the matrix $\delta[i][j]$ of shortest-path distances from $i$ to $j$ for every ordered pair.

Weight matrix $W$: $W[i][i] = 0$, $W[i][j]$ the weight of the edge $i \to j$, and $\infty$ if there is no such edge.

Intermediate vertex. A vertex of a path other than its two ends.

State. $D^{(k)}[i][j]$ is the weight of a shortest path from $i$ to $j$ all of whose intermediate vertices are in $\{0, 1, \ldots, k\}$ ($D^{(-1)} = W$: no intermediate vertex allowed, direct edges only).

How it works

The recurrence

A shortest path from $i$ to $j$ with intermediate vertices in $\{0, \ldots, k\}$ either does not use vertex $k$ (then it is a shortest path with intermediates in $\{0, \ldots, k-1\}$) or uses it once (a shortest path is simple): it consists of a shortest path from $i$ to $k$ and a shortest path from $k$ to $j$, both with intermediates in $\{0, \ldots, k-1\}$:

$D^{(k)}[i][j] = \min\bigl(D^{(k-1)}[i][j],\ D^{(k-1)}[i][k] + D^{(k-1)}[k][j]\bigr).$

The answer is $D^{(V-1)}$. The code needs only one matrix, updated in place:

for (k = 0; k < V; k++)
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            if (d[i][k] + d[k][j] < d[i][j])
                d[i][j] = d[i][k] + d[k][j];

In-place update is safe: during iteration $k$ the row $k$ and the column $k$ do not change (without negative cycles, $D[k][k] = 0$, so $D[i][k] + D[k][k] = D[i][k]$), so the values read are those of $D^{(k-1)}$. Time $\Theta(V^3)$ (exactly $V^3$ executions of the innermost test), space $\Theta(V^2)$. The loop over $k$ must be the outermost: a loop order with $k$ inside gives wrong answers.

The page graph, step by step

The graph has $5$ vertices and the edges $0 \to 1\,(3)$, $0 \to 2\,(5)$, $1 \to 2\,(-2)$, $1 \to 3\,(4)$, $2 \to 3\,(2)$, $3 \to 0\,(6)$, $3 \to 4\,(1)$, $4 \to 1\,(2)$. The program prints the matrix before the loop and after each value of $k$; $\infty$ is written inf.

#include <stdio.h>
 
#define N 5
#define INF 1000000
 
static void show(int d[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (d[i][j] >= INF) printf(" inf");
            else printf(" %3d", d[i][j]);
        }
        printf("\n");
    }
}
 
int main(void) {
    int d[N][N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) d[i][j] = i == j ? 0 : INF;
    d[0][1] = 3; d[0][2] = 5; d[1][2] = -2; d[1][3] = 4; d[2][3] = 2; d[3][0] = 6; d[3][4] = 1; d[4][1] = 2;
    printf("D0 (only direct edges):\n");
    show(d);
    for (int k = 0; k < N; k++) {                        /* allow vertex k as an intermediate vertex */
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
        printf("after k = %d:\n", k);
        show(d);
    }
    int negative = 0;
    for (int i = 0; i < N; i++) if (d[i][i] < 0) negative = 1;
    printf("negative cycle: %s\n", negative ? "yes" : "no");
    return 0;
}

D0 (only direct edges):
   0   3   5 inf inf
 inf   0  -2   4 inf
 inf inf   0   2 inf
   6 inf inf   0   1
 inf   2 inf inf   0
after k = 0:
   0   3   5 inf inf
 inf   0  -2   4 inf
 inf inf   0   2 inf
   6   9  11   0   1
 inf   2 inf inf   0
after k = 1:
   0   3   1   7 inf
 inf   0  -2   4 inf
 inf inf   0   2 inf
   6   9   7   0   1
 inf   2   0   6   0
after k = 2:
   0   3   1   3 inf
 inf   0  -2   0 inf
 inf inf   0   2 inf
   6   9   7   0   1
 inf   2   0   2   0
after k = 3:
   0   3   1   3   4
   6   0  -2   0   1
   8  11   0   2   3
   6   9   7   0   1
   8   2   0   2   0
after k = 4:
   0   3   1   3   4
   6   0  -2   0   1
   8   5   0   2   3
   6   3   1   0   1
   8   2   0   2   0
negative cycle: no

The animation below shows the same run one improvement at a time: first the matrix $D^{(-1)}$ of direct edges, then for each $k$ a step that says which vertex is now allowed and one step for every entry that improves, with the path that gives the improvement.

For example, with $k = 1$ the entry $D[0][2]$ improves from $5$ to $1$: the path $0 \to 1 \to 2$ costs $3 + (-2)$, cheaper than the direct edge. With $k = 3$ many entries become finite for the first time: vertex $3$ links the vertices that could reach it with those it can reach. The final matrix has no negative diagonal entry, so the graph has no negative cycle.

Negative edges and negative cycles

Floyd-Warshall works with negative edges as long as there is no negative cycle. If there is one, some diagonal entry $D[i][i]$ becomes negative (a path from $i$ back to $i$ of negative weight): check the diagonal after the loops. (Example: edges $0 \to 1\,(1)$, $1 \to 2\,(-3)$, $2 \to 0\,(1)$ give $D[0][0] = -1$.) In that case the other entries may be meaningless.

Recovering the paths

Keep a second matrix $\text{next}[i][j]$ (the first vertex after $i$ on a shortest path to $j$), initialised to $j$ for every edge $i \to j$; whenever $D[i][j]$ improves through $k$ set $\text{next}[i][j] = \text{next}[i][k]$. A path is then read by following $\text{next}$ from $i$ until $j$. (Equivalently a predecessor matrix.)

Transitive closure (Warshall's algorithm)

To decide only whether $j$ is reachable from $i$, use a Boolean matrix $R$ with $R[i][i] = 1$ and $R[i][j] = 1$ for each edge, and the same three loops with the update $R[i][j] = R[i][j] \lor (R[i][k] \land R[k][j])$. After iteration $k$, $R[i][j] = 1$ exactly if there is a path from $i$ to $j$ with intermediate vertices in $\{0, \ldots, k\}$. The result is the transitive closure of the edge relation, in $\Theta(V^3)$ time (checked against searches from every vertex). Searching from every vertex does the same job in $\Theta(V(V + E))$, which is faster for sparse graphs.

Which algorithm for all pairs?

For dense graphs ($E \approx V^2$) Floyd-Warshall's $\Theta(V^3)$ is as good as any and much simpler; for sparse graphs $V$ runs of Dijkstra (or Johnson's algorithm if there are negative edges) are faster.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Floyd-Warshall is a dynamic program over the allowed intermediate vertices. It computes for all pairs what Dijkstra and Bellman-Ford compute for one source, and its Boolean form computes the reachability that depth-first search and strongly connected components find by searching.

PYQs

The Asymptotic Notation of computing the
transitive closure of a binary relation on a set of n
elements is known to be:

Consider the weighted undirected graph with 4
vertices, where the weight of edge {i, j} is given by
the entry W ij in the matrix W.

Self-check

Revision card

References