Floyd-Warshall Algorithm

Overview

The Floyd-Warshall algorithm is a dynamic programming algorithm for finding shortest paths between all pairs of vertices in a weighted graph. It works on both directed and undirected graphs, and can handle negative edge weights (but not negative cycles).

Unlike Dijkstra's and Bellman-Ford which find shortest paths from a single source, Floyd-Warshall finds shortest paths between every pair of vertices in one execution. It uses a dynamic programming approach, building up solutions by considering intermediate vertices.

The algorithm is particularly useful when you need shortest paths between all pairs of vertices, such as in network analysis, social network analysis, and transportation planning.

Floyd-Warshall is one of the most elegant algorithms in computer science. Its three nested loops fit on a single line each, and yet they compute shortest paths between every pair of vertices in a graph, a problem that on the face of it seems to require running a single-source algorithm V times, once from each starting vertex. Floyd-Warshall's insight, encoded in the six-line implementation, is that if you consider intermediate vertices one at a time, you never need to compute anything twice. The compactness of the algorithm relative to what it computes is one of those small aesthetic pleasures that recurs whenever people teach it.

History and Attribution

The algorithm has one of the more tangled naming histories in the field, which is worth knowing because it appears under different names in different textbooks.

The algorithm was independently discovered several times in the late 1950s and early 1960s. Bernard Roy published it in a 1959 French paper on graph analysis; Robert Floyd published it in 1962 in the Communications of the ACM as "Algorithm 97: Shortest Path"; Stephen Warshall published a very similar algorithm the same year for computing the transitive closure of a graph, which is the same recurrence with logical operations instead of min-plus. Peter Ingerman noted in 1962 that Warshall's transitive-closure algorithm and Floyd's shortest-path algorithm were structurally identical. The modern name credits both Floyd (for shortest paths) and Warshall (for the transitive-closure variant), while Roy's earlier paper is sometimes acknowledged with the name Roy–Floyd–Warshall or Floyd–Warshall–Roy.

The underlying dynamic-programming recurrence is older still. Bellman's principle of optimality, published in 1957, provides the framework for reasoning about shortest paths through intermediate vertices. Floyd's contribution was to recognise that this recurrence could be evaluated in O(V³) with three simple nested loops in the correct order, a beautifully compact realisation of a general dynamic-programming schema.

Why the Order of the Loops Matters

The Floyd-Warshall algorithm is often taught as "just three nested loops," but the fact that the outer loop is over the intermediate vertex k, not over i or j, is the crucial insight. Getting the loop order wrong turns a correct O(V³) algorithm into one that produces wrong answers.

The invariant: after iteration k of the outer loop, dist[i][j] holds the length of the shortest path from i to j that uses only vertices from the set {0, 1, ..., k} as intermediate vertices (i and j themselves are always allowed as endpoints). At k = −1 (before any outer iterations), the only allowed paths are direct edges, which is what the initial matrix contains. At k = V−1 (after all outer iterations), every vertex is allowed as an intermediate, so the matrix contains true shortest paths.

The step: when we process outer iteration k, we ask, for each pair (i, j): is there a shorter path from i to j that goes through k, using only vertices from {0, ..., k−1} in the two halves? The shortest such path is dist[i][k] + dist[k][j], which by the inductive hypothesis is already correct because both halves use only vertices from {0, ..., k−1}. So the update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) correctly extends the invariant from k−1 to k.

Why the outer loop must be k: if you put i or j on the outside, the dist[i][k] and dist[k][j] values that you read at some point will have been overwritten from later iterations, and the values will no longer refer to paths using only vertices from {0, ..., k−1}. This is a subtle bug that produces plausible-looking but incorrect answers. Debugging it is a rite of passage for people implementing Floyd-Warshall from memory.

A helpful mnemonic: think of the outer loop as "gradually admitting more vertices as allowed transit points." Each new value of k unlocks a new possible intermediate, and the inner loops let every source-destination pair take advantage of the new freedom.

Detecting Negative Cycles

Floyd-Warshall is the natural home for a beautiful negative-cycle detection technique that Dijkstra's cannot match: check the diagonal of the distance matrix.

Initially dist[i][i] = 0 for every vertex i. If, after the algorithm runs, dist[i][i] is negative for some i, that means there is a path from i back to i whose total weight is negative, which is exactly a negative cycle passing through i. So a single scan of the diagonal after Floyd-Warshall finishes tells you whether the graph has any negative cycle, and identifies which vertices lie on one. This is strictly more informative than what Bellman-Ford tells you, which is only whether a negative cycle exists reachable from a specific source vertex.

An important caveat: if any negative cycle exists, the shortest-path values in the matrix are meaningless for any pair of vertices that can reach the cycle and be reached from it. The concept of shortest path breaks down when you can drive the distance to negative infinity by looping around a negative cycle. In practice, check the diagonal first; if it is clean, the rest of the matrix is trustworthy.

Real-World Applications

All-Pairs Reachability (Transitive Closure)

Warshall's original 1962 algorithm computed the transitive closure of a directed graph, the matrix reach[i][j] which is true if and only if j is reachable from i. The algorithm is structurally identical to Floyd-Warshall for shortest paths, but replaces "min" with "OR" and "+" with "AND." Transitive closure has real uses in database query optimisation (which tables can be joined?), in software dependency analysis (does module A eventually depend on module B?), and in inheritance analysis in object-oriented type systems.

Small-Diameter Network Analysis

The "six degrees of Kevin Bacon" and similar problems compute the pairwise distance in a social network. For networks with a few hundred to a few thousand vertices, Floyd-Warshall is simple and fast enough. Larger networks need Johnson's algorithm (Bellman-Ford + Dijkstra) for better complexity on sparse graphs.

Regex to NFA to DFA Conversion

Kleene's theorem on regular languages is proved constructively using an algorithm strikingly similar to Floyd-Warshall, iteratively "eliminating" states in a finite automaton by considering paths that pass through each state as an intermediate. This is not usually presented as an application of Floyd-Warshall, but the loop structure is essentially the same.

Routing in Small Networks

Some routing protocols in small managed networks precompute all-pairs shortest paths with Floyd-Warshall and consult the table for each packet. On networks of tens of routers this is entirely practical; the O(V³) build cost is a one-time setup, and lookups are then O(1). Larger networks use single-source algorithms per packet or link-state protocols like OSPF.

How It Works

The algorithm uses dynamic programming with the following recurrence relation:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

For each intermediate vertex k, it checks if going through k gives a shorter path from i to j.

Initialize: Create distance matrix with direct edge weights
Iterate: For each vertex k (0 to V-1):
- For each pair (i, j), check if path i → k → j is shorter
- Update dist[i][j] if shorter path found
Result: Distance matrix contains shortest paths between all pairs

Floyd-Warshall Algorithm Pseudocode


FloydWarshall(graph):
    n = number of vertices
    dist = n × n matrix initialized with:
        dist[i][j] = weight(i, j) if edge exists
        dist[i][j] = ∞ if no edge
        dist[i][i] = 0
    
    for k = 0 to n-1:
        for i = 0 to n-1:
            for j = 0 to n-1:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

Implementation


def floyd_warshall(graph):
    """
    graph: adjacency matrix (n × n)
           graph[i][j] = weight if edge exists, ∞ if no edge, 0 if i == j
    Returns: distance matrix with shortest paths between all pairs
    """
    n = len(graph)
    dist = [row[:] for row in graph]  # Copy graph
    
    # Floyd-Warshall algorithm
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

def floyd_warshall_with_paths(graph):
    """Floyd-Warshall with path reconstruction"""
    n = len(graph)
    dist = [row[:] for row in graph]
    next_vertex = [[None] * n for _ in range(n)]
    
    # Initialize next matrix
    for i in range(n):
        for j in range(n):
            if graph[i][j] != float('inf'):
                next_vertex[i][j] = j
    
    # Floyd-Warshall
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        next_vertex[i][j] = next_vertex[i][k]
    
    return dist, next_vertex

def reconstruct_path(next_vertex, start, end):
    """Reconstruct path from next matrix"""
    if next_vertex[start][end] is None:
        return []
    
    path = [start]
    while start != end:
        start = next_vertex[start][end]
        path.append(start)
    return path

Complexity Analysis

Time Complexity: O(V³) - three nested loops over all vertices
Space Complexity: O(V²) - for distance matrix

The algorithm is simple and cache-friendly, three tight nested loops over a contiguous matrix, but the cubic time makes it practical only up to roughly V = 1000–2000 on modern hardware. Note the loop order matters: k must be the outermost loop, because the recurrence requires all paths using intermediates {0..k-1} to be final before considering k.

For sparse graphs, use Johnson's algorithm instead. It reweights the graph with a single Bellman-Ford pass so that all edge weights become non-negative while shortest paths are preserved, then runs Dijkstra's from every vertex. That gives O(V·E + V² log V), which beats O(V³) whenever E is much smaller than V², and unlike repeated Dijkstra alone, it still handles negative edge weights. Floyd-Warshall remains the better choice for dense graphs and for its sheer simplicity.

Detecting Negative Cycles

After running Floyd-Warshall, check for negative cycles by looking for negative values on the diagonal. dist[i][i] starts at 0, so if it ends up below 0 there must be a path from i back to itself with negative total weight.

If a negative cycle exists, the rest of the matrix is not trustworthy, distances for any pair whose shortest path passes through the cycle are unbounded below, and what the table contains is just however far the relaxation happened to get. Check the diagonal before using any other entry.


def has_negative_cycle(dist):
    """Check if graph has negative cycle"""
    n = len(dist)
    for i in range(n):
        if dist[i][i] < 0:
            return True
    return False

Example

Finding shortest paths between all pairs:

Graph (4 vertices, directed):

    0 --(4)--> 1
    ^          |
    |         (2)
   (1)         |
    |          v
    +--------- 2 --(3)--> 3

Edges: 0->1 (4), 1->2 (2), 2->0 (1), 2->3 (3)

Initial distance matrix:
    0   1   2   3
0   0   4   ∞   ∞
1   ∞   0   2   ∞
2   1   ∞   0   3
3   ∞   ∞   ∞   0

After k=0 (considering vertex 0 as intermediate):
    0   1   2   3
0   0   4   ∞   ∞
1   ∞   0   2   ∞
2   1   5   0   3
3   ∞   ∞   ∞   0

After k=1 (considering vertex 1 as intermediate):
    0   1   2   3
0   0   4   6   ∞
1   ∞   0   2   ∞
2   1   5   0   3
3   ∞   ∞   ∞   0

After k=2 (considering vertex 2 as intermediate):
    0   1   2   3
0   0   4   6   9
1   3   0   2   5
2   1   5   0   3
3   ∞   ∞   ∞   0

After k=3 (considering vertex 3 as intermediate):
    (no changes)

Final result: All-pairs shortest paths

When to Use Floyd-Warshall

Floyd-Warshall is ideal when:

You need shortest paths between all pairs of vertices
Graph is small to medium (V < 500)
Graph can have negative weights (but not negative cycles)
You need a simple, easy-to-implement solution
Dense graphs where most pairs are connected

Consider alternatives when:

Graph is large and sparse → Use Johnson's algorithm (Bellman-Ford reweighting + Dijkstra from each vertex)
Only need single-source shortest paths → Use Dijkstra's or Bellman-Ford
Sparse graph → Dijkstra/Bellman-Ford may be more efficient

Floyd-Warshall vs Other Algorithms

Algorithm	Pairs	Time Complexity	Best For
Dijkstra's	Single source	O((V + E) log V)	Non-negative weights
Bellman-Ford	Single source	O(V × E)	Negative weights
Floyd-Warshall	All pairs	O(V³)	All-pairs, small graphs

Real-World Applications

Network Analysis: Finding shortest paths in computer networks
Social Networks: Computing distances between all users
Transportation: Finding shortest routes between all cities
Game Development: Precomputing distances for pathfinding
Clustering: Computing distance matrices for clustering algorithms

Related Algorithms

Explore other searching algorithms:

Dijkstra's Algorithm - Single-source shortest paths
Bellman-Ford Algorithm - Negative weights support
A* Algorithm - Heuristic-based search
Back to Graph Algorithms Overview