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\).

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)\)).