Floyd-Warshall Algorithm — All-Pairs Shortest Paths Explained

The Story That Explains Floyd-Warshall

The Floyd-Warshall algorithm, described in CLRS Chapter 25, solves the All-Pairs Shortest Paths (APSP) problem. Unlike Dijkstra (one source → all destinations) or Bellman-Ford (one source, handles negatives), Floyd-Warshall finds shortest paths between every possible pair of vertices in a single run — including graphs with negative edge weights, as long as there are no negative-weight cycles.

Formal Definition & The Recurrence

Let G = (V, E) be a weighted directed graph with n vertices numbered 1 through n. Let w(i, j) be the weight of edge (i→j).

Animated Worked Example — Step by Step

Let's trace Floyd-Warshall on a concrete 4-vertex graph. Watch the distance matrix evolve as each intermediate vertex k is processed. Click Next Step to advance one iteration at a time.

The CLRS Pseudocode — Line by Line

Below is the CLRS pseudocode for Floyd-Warshall annotated with exactly what each line does. Click the code lines in the interactive tracer below to see the explanation for that specific line.

FLOYD-WARSHALL(W)
  n = W.rows
  D⁰ = W
  for k = 1 to n
    for i = 1 to n
      for j = 1 to n
        dk[i][j] = min(dk-1[i][j],
                      dk-1[i][k] + dk-1[k][j])
  return Dn

Python Implementation with Code Animation

Below is a clean, production-ready Python implementation matching the CLRS description. Use the Step Through button to advance one major operation at a time and see exactly what's happening inside the algorithm.

import math

def floyd_warshall(W):
    # W: n×n weight matrix (use math.inf for no edge)
    n = len(W)
    D = [row[:] for row in W]   # deep copy
    pi = [[None]*n for _ in range(n)] # predecessor

    # Initialise predecessor matrix
    for i in range(n):
        for j in range(n):
            if i != j and W[i][j] != math.inf:
                pi[i][j] = i  # direct edge exists

    for k in range(n):          # relay vertex
        for i in range(n):      # source
            for j in range(n):  # destination
                through_k = D[i][k] + D[k][j]
                if through_k < D[i][j]:
                    D[i][j] = through_k
                    pi[i][j] = pi[k][j]  # update predecessor

    # Detect negative cycles (optional safety check)
    for i in range(n):
        if D[i][i] < 0:
            raise ValueError("Negative-weight cycle detected")

    return D, pi

Path Reconstruction with the Predecessor Matrix

The distance matrix D tells you how far. The predecessor matrix π tells you how to get there. Here's the CLRS path reconstruction function and a concrete example.

def print_path(pi, i, j):
    # Print the shortest path from vertex i to vertex j
    # pi: predecessor matrix returned by floyd_warshall()
    # Vertices are 0-indexed internally
    if i == j:
        print(i + 1)  # display 1-indexed
    elif pi[i][j] is None:
        print(f"No path from {i+1} to {j+1}")
    else:
        print_path(pi, i, pi[i][j])  # recurse through predecessors
        print(j + 1)

# Using the 4-vertex example from Section 03
import math
INF = math.inf
W = [
    [0,    3,   8,   INF],
    [INF,  0,   INF, 1  ],
    [INF,  4,   0,  -5  ],
    [2,    INF, INF, 0  ]
]
D, pi = floyd_warshall(W)

print(f"Shortest 1→4: distance = {D[0][3]}")
print_path(pi, 0, 3)   # 0-indexed: vertex 1→4

Complexity Analysis

Negative Cycles — Detection & Why They Matter

CLRS Theorem 25.1 states: after running Floyd-Warshall, the graph contains a negative-weight cycle if and only if there exists a vertex i such that D[i][i] < 0. Simply checking the diagonal is sufficient.

Visual Diagram — The DP "Relay" Concept

The diagram below illustrates the key insight: at step k, we test whether routing through vertex k as a relay improves any existing path. The purple arc shows the "via k" route.

Real-World Use Cases & Benefits

Bonus: Transitive Closure (CLRS §25.2)

CLRS Section 25.2 presents a variant that computes the transitive closure of a directed graph — answering "can vertex j be reached from vertex i?" for all pairs. The structure is identical to Floyd-Warshall but uses Boolean algebra instead of arithmetic.

def transitive_closure(adj):
    # adj: n×n adjacency matrix (True/False or 1/0)
    # Returns: n×n reachability matrix T
    n = len(adj)
    # T[i][j] = True if j is reachable from i
    T = [[adj[i][j] or (i == j) for j in range(n)] for i in range(n)]

    for k in range(n):          # relay vertex k
        for i in range(n):
            for j in range(n):
                # Reachable directly OR via k
                T[i][j] = T[i][j] or (T[i][k] and T[k][j])
    return T

# Example: 4-vertex DAG
adj = [
    [False, True,  False, False],  # 1→2
    [False, False, True,  False],  # 2→3
    [False, False, False, True ],  # 3→4
    [False, False, False, False],  # no outgoing
]
T = transitive_closure(adj)
print(f"Can 1 reach 4? {T[0][3]}")  # True: 1→2→3→4
print(f"Can 4 reach 1? {T[3][0]}")  # False: no back edges

CLRS Chapter 25 Context — Where Floyd-Warshall Fits

Golden Rules — Floyd-Warshall in Practice

Algorithm Comparison — APSP Methods