Floyd-Warshall Algorithm: All-Pairs Shortest Paths

The All-Pairs Shortest Path Problem

Given a weighted directed graph $G = (V, E, w)$, find the shortest path between every pair of vertices $(i, j)$.

Applications:
- Finding if any path exists between all pairs (routing tables)
- Computing transitive closure (reachability)
- Detecting negative cycles

Algorithm Specification

Input: Directed weighted graph with $n$ vertices (adjacency matrix $W$)
Output: Matrix $D$ where $D[i][j]$ = shortest path from $i$ to $j$
Precondition: No negative-weight cycles

Floyd-Warshall Algorithm

Core Idea (Dynamic Programming)

For each intermediate vertex $k$, consider whether routing from $i$ to $j$ via $k$ is shorter than the current best known path from $i$ to $j$.

$$D[i][j] = \min(D[i][j],\; D[i][k] + D[k][j])$$

This is applied for $k = 0, 1, \ldots, n-1$ (each vertex as potential intermediate).

Algorithm

ALGORITHM FloydWarshall(W, n)
    D ← copy of W   // initialise: D[i][j] = w(i,j) if edge exists, else ∞
    for i ← 0 to n-1 do
        D[i][i] ← 0   // distance from vertex to itself is 0
    end for

    for k ← 0 to n-1 do            // try each vertex as intermediate
        for i ← 0 to n-1 do
            for j ← 0 to n-1 do
                if D[i][k] + D[k][j] < D[i][j] then
                    D[i][j] ← D[i][k] + D[k][j]
                end if
            end for
        end for
    end for
    return D

Time Complexity: $O(n^3)$

Three nested loops, each running $n$ times.

Space Complexity: $O(n^2)$

The $n \times n$ distance matrix.

Worked Example

3-vertex graph: 0→1 (3), 0→2 (8), 1→2 (1), 2→0 (2)

Initial $D$:

    0    1    2
0 [ 0,   3,   8 ]
1 [ ∞,   0,   1 ]
2 [ 2,   ∞,   0 ]

After $k=0$ (vertex 0 as intermediate):
- $D[1][2]$ stays 1 (no improvement via 0)
- $D[2][1]$ = $D[2][0] + D[0][1]$ = 2 + 3 = 5

After $k=1$ (vertex 1 as intermediate):
- $D[0][2]$ = min(8, $D[0][1]+D[1][2]$) = min(8, 3+1) = 4

After $k=2$ (vertex 2 as intermediate):
- $D[0][1]$ = min(3, $D[0][2]+D[2][1]$) = min(3, 4+5) = 3 (no improvement)
- $D[1][0]$ = $D[1][2]+D[2][0]$ = 1+2 = 3

Application: Transitive Closure

The transitive closure of a directed graph answers: “Is there any path from vertex $i$ to vertex $j$?”

Modify Floyd-Warshall to use Boolean values:

ALGORITHM TransitiveClosure(graph, n)
    T ← Boolean matrix (T[i][j] = true if edge i→j exists)
    for k ← 0 to n-1 do
        for i ← 0 to n-1 do
            for j ← 0 to n-1 do
                T[i][j] ← T[i][j] OR (T[i][k] AND T[k][j])
            end for
        end for
    end for
    return T

If $T[i][j] = \text{true}$ after running this algorithm, there exists a path from $i$ to $j$.

Negative Cycle Detection

If $D[i][i] < 0$ for any vertex $i$ after running Floyd-Warshall, there is a negative-weight cycle reachable from $i$.

Comparison with Other Shortest Path Algorithms

EXAM TIP: Floyd-Warshall is always $O(n^3)$ regardless of graph density. For all-pairs problems on dense graphs this is efficient; running Dijkstra’s $n$ times is better for sparse graphs with non-negative weights ($O(V(V+E)\log V)$).