Warshall's Algorithm (Transitive Closure)

Reachability and Transitive Closure

A directed edge answers a one-step question: “can $i$ move directly to $j$?” Transitive closure answers the all-steps version: “can $i$ reach $j$ through a directed path of any permitted length?” The output is a Boolean matrix with one row per source and one column per destination.

The Boolean Bridge Rule

When vertex $k$ becomes an allowed intermediate, a pair $(i,j)$ is reachable in one of two ways: it was already reachable without $k$, or a route can be split at $k$ into $i\leadsto k$ and $k\leadsto j$.

This gives the familiar three nested loops. The $k$ loop must be outermost because it controls the set of legal intermediate vertices. The $i$ and $j$ loops may be interchanged without changing the invariant.

The DP Invariant and Correctness

Let $R^{(k)}[i][j]$ mean that a path from $i$ to $j$ exists whose internal vertices come only from $\{0,1,\ldots,k\}$. Endpoints $i$ and $j$ do not need to be in that set.

Why this is complete: take any allowed path from $i$ to $j$. Either it does not use $k$ internally, so the first term already knows it, or it uses $k$. Split at one occurrence of $k$: both halves use only earlier allowed intermediates, so the second term detects them. Conversely, joining two real paths through $k$ produces a real walk from $i$ to $j$, hence valid reachability.

The $O(V^2)$ table can be updated in place. During phase $k$, the entries read from row/column $k$ already express reachability using intermediates through $k$; Boolean OR is monotone, and using those newly confirmed entries cannot invent a path outside the same permitted set.

Worked Matrix Trace

Use edges $1\to2$, $2\to3$, $3\to1$, and $3\to4$. For this trace, the diagonal begins false: reachability requires at least one edge. That lets the algorithm discover $R[1][1]$, $R[2][2]$, and $R[3][3]$ as evidence of the directed cycle.

Diagonal Semantics: Two Valid Questions

“Does a vertex reach itself?” has two conventions, and the initialization decides which one the matrix answers.

Neither convention is universally “the” correct one. Dependency queries often want reflexivity (“a module depends on itself through zero steps” may be convenient); cycle analysis wants the strict form. Name the choice in the API instead of hiding it in initialization.

Warshall and Floyd–Warshall

The algorithms share the same intermediate-vertex dynamic program but operate over different algebras. Warshall asks whether a route exists; Floyd–Warshall asks for the cheapest route.

If an all-pairs distance matrix has already been computed and no negative-cycle ambiguity applies, finite distance implies reachability. When reachability is the only goal, the Boolean formulation is simpler and particularly amenable to word-level bitset acceleration.

Implementation

The three-language versions expose a reflexive switch. They copy reachability into an $n\times n$ Boolean matrix, then update it in place with $k$ outermost. The early if reach[i][k] guard skips an entire row operation when $i$ cannot use $k$ as a bridge.

def warshalls_algorithm(n, edges, reflexive=True):
    """
    n: number of vertices (0-indexed)
    edges: list of (u, v) directed edges
    reflexive=True includes zero-edge paths i -> i.
    Returns an n x n boolean reachability matrix.
    """
    reach = [[False] * n for _ in range(n)]

    if reflexive:
        for i in range(n):
            reach[i][i] = True
    for u, v in edges:
        reach[u][v] = True

    for k in range(n):
        for i in range(n):
            if reach[i][k]:
                for j in range(n):
                    reach[i][j] = reach[i][j] or reach[k][j]

    return reach

# Example: 1->2->3->1 (cycle), plus 3->4  (0-indexed: 0->1->2->0, 2->3)
n = 4
edges = [(0, 1), (1, 2), (2, 0), (2, 3)]
result = warshalls_algorithm(n, edges, reflexive=False)

print("Reachability matrix:")
for row in result:
    print([int(x) for x in row])

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

vector<vector<bool>> warshallsAlgorithm(
        int n, const vector<pair<int,int>>& edges, bool reflexive = true) {
    vector<vector<bool>> reach(n, vector<bool>(n, false));

    if (reflexive)
        for (int i = 0; i < n; ++i) reach[i][i] = true;
    for (const auto& e : edges) reach[e.first][e.second] = true;

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (reach[i][k]) {
                for (int j = 0; j < n; j++) {
                    reach[i][j] = reach[i][j] || reach[k][j];
                }
            }
        }
    }
    return reach;
}

int main() {
    int n = 4;
    vector<pair<int,int>> edges = {{0,1}, {1,2}, {2,0}, {2,3}};
    auto reach = warshallsAlgorithm(n, edges, false);

    cout << "Reachability matrix:" << endl;
    for (auto& row : reach) {
        for (bool b : row) cout << b << " ";
        cout << endl;
    }
    return 0;
}

import java.util.*;

public class WarshallsAlgorithm {
    public static boolean[][] solve(int n, int[][] edges, boolean reflexive) {
        boolean[][] reach = new boolean[n][n];

        if (reflexive)
            for (int i = 0; i < n; ++i) reach[i][i] = true;
        for (int[] e : edges) reach[e[0]][e[1]] = true;

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (reach[i][k]) {
                    for (int j = 0; j < n; j++) {
                        reach[i][j] = reach[i][j] || reach[k][j];
                    }
                }
            }
        }
        return reach;
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{0,1}, {1,2}, {2,0}, {2,3}};
        boolean[][] reach = solve(n, edges, false);

        System.out.println("Reachability matrix:");
        for (boolean[] row : reach) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Bitset Acceleration

The scalar inner loop says: if row $i$ reaches $k$, merge every true destination from row $k$ into row $i$. A bitset stores an entire row in machine words, turning $V$ Boolean OR operations into a handful of word-level ORs. In Python, one arbitrary-precision integer can act as the row bitset.

def warshall_bitset(n, edges, reflexive=True):
    rows = [0] * n
    if reflexive:
        for i in range(n):
            rows[i] |= 1 << i
    for u, v in edges:
        rows[u] |= 1 << v

    for k in range(n):
        bit_k = 1 << k
        row_k = rows[k]
        for i in range(n):
            if rows[i] & bit_k:
                rows[i] |= row_k
    return rows

def reaches(rows, source, target):
    return bool(rows[source] & (1 << target))

Bit packing does not change the information-theoretic requirement: the full answer still contains $V^2$ bits. On a word-RAM with word size $w$, it reduces the update work toward $O(V^3/w)$ word operations and stores the matrix in $O(V^2/w)$ words. Actual speedup depends on language, representation, graph density, and cache behavior.

Store a Path Witness, Not Only a Boolean

A true matrix cell proves existence but does not explain the route. Add a nextHop matrix. For a direct edge $u\to v$, the first hop is $v$. When $(i,j)$ becomes reachable through $k$, copy the first hop used to reach $k$ from $i$.

def warshall_with_witness(n, edges, reflexive=True):
    reach = [[False] * n for _ in range(n)]
    next_hop = [[None] * n for _ in range(n)]

    if reflexive:
        for i in range(n):
            reach[i][i] = True
            next_hop[i][i] = i
    for u, v in edges:
        reach[u][v] = True
        next_hop[u][v] = v

    for k in range(n):
        for i in range(n):
            if not reach[i][k]:
                continue
            for j in range(n):
                if not reach[i][j] and reach[k][j]:
                    reach[i][j] = True
                    next_hop[i][j] = next_hop[i][k]
    return reach, next_hop

def reconstruct_path(next_hop, source, target):
    if next_hop[source][target] is None:
        return []
    path = [source]
    while source != target:
        source = next_hop[source][target]
        path.append(source)
    return path

The first witness discovered is retained; a different vertex order may produce a different valid route. This matrix reconstructs paths between distinct endpoints and the zero-edge reflexive witness $[i]$. If you need an explicit nonempty cycle for a true strict-diagonal cell, retain predecessor information or start reconstruction from one of the cycle's outgoing edges.

Complexity and When to Use It

The cubic loop is independent of $E$ after initialization, making Warshall attractive when the graph is dense and most or all of the $V^2$ reachability answers will be queried. It is often wasteful when the graph is sparse or only a few sources matter.

Real-World Applications

Precomputed closure is most useful when the relation changes rarely but indirect-membership questions arrive frequently.

Pitfalls and Implementation Checklist

Exercises

1. Run the four-vertex example in both diagonal modes and explain the only cell that differs.
2. Prove the recurrence by induction on the set of allowed intermediate vertices.
3. Find a counterexample for the loop order for i, for j, for k.
4. Use mutual reachability to group the example's strongly connected components.
5. Extend the witness version to return one explicit directed cycle for each true strict-diagonal cell.
6. Benchmark scalar and bitset versions on dense and sparse graphs of increasing size.
7. Challenge: after adding one new edge $a\to b$ to an existing closure, derive which rows and columns can be updated without recomputing from scratch.

Historical Note

Stephen Warshall published the Boolean-matrix closure algorithm in 1962; closely related work by Bernard Roy appeared earlier. The same three-loop dynamic-programming pattern is also associated with Floyd's all-pairs shortest-path formulation. The family is a classic example of one recurrence surviving while its value domain and operators change.