Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Transitive closure and Warshall's algorithm

How to compute the transitive closure (reachability) of a relation or directed graph and how Warshall's algorithm finds it in O(n^3) time using boolean matrix updates.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Transitive closure tells an engineer which nodes (states, modules, processes) can reach which others by following available edges or transitions. This is used in program analysis (reachability, call graphs), database query optimization (recursive queries), network routing and dependency analysis.

Key ideas

  • Adjacency matrix: For a relation R on an n-element set with vertices numbered 1..n, the adjacency matrix A = [a_ij] is the n×n matrix with a_ij = 1 if (i,j) in R (an edge i→j exists), and a_ij = 0 otherwise. We treat entries as boolean (1 = true, 0 = false).
  • Path and reachability: A path of length k from i to j is a sequence i = v_0, v_1, ..., v_k = j such that (v_{t-1},v_t) in R for each t = 1..k. Vertex j is reachable from i if there exists a path of length ≥1 from i to j.
  • Transitive relation: A relation T is transitive if whenever (a,b) in T and (b,c) in T then (a,c) in T.
  • Transitive closure: The transitive closure of R, written R^+ or Tc(R), is the smallest transitive relation that contains R. Equivalently, R^+ = ⋃_{k≥1} R^k where R^k is the k-fold composition (paths of length k). If we also include reflexive pairs (i,i) for all i, we get the reflexive transitive closure R* = I ∪ R^+ (often used when zero-length paths count).

Exact statements and assumptions used below:

  • For an n-vertex relation with adjacency matrix A, define boolean matrix multiplication: (B·C)[i,j] = OR_{t=1..n} (B[i,t] AND C[t,j]). Then A^k (boolean power) corresponds to reachability by paths of length exactly k.
  • Then transitive closure boolean matrix T satisfies T = A OR A^2 OR ... OR A^n (finite because n is finite; for i != j, paths of length at most n-1 suffice, but to include i->i via a simple cycle you may need length n).

Warshall's algorithm (statement and correctness idea):

  • Let R^{(0)} = A. For k = 1..n, define R^{(k)} by for all i,j: R^{(k)}[i,j] = R^{(k-1)}[i,j] OR (R^{(k-1)}[i,k] AND R^{(k-1)}[k,j]).
  • After iteration k, R^{(k)}[i,j] is true exactly when there is a path from i to j whose intermediate vertices (all internal vertices, not endpoints) are all from the set {1,..,k}.
  • After k = n, no intermediate vertices are excluded, so R^{(n)} is the transitive closure R^+.

Proof sketch by induction on k (typical university answer):

  • Base k=0: R^{(0)} records paths that use no intermediate vertices (only direct edges) — correct.
  • Inductive step: Suppose property holds for k-1. A path that uses intermediates from {1..k} either uses none of vertex k as an intermediate (so already in R^{(k-1)}) or it does use k at least once. If it uses k, split path i→...→k and k→...→j; both subpaths use intermediates only in {1..k-1}; so R^{(k-1)}[i,k] and R^{(k-1)}[k,j] hold. Thus the OR formula captures both cases. This proves correctness.

Complexity: Warshall runs three nested loops over n, so time complexity is O(n^3); space O(n^2) to store the boolean matrix.

What to draw in diagrams for an exam answer:

  • Draw a directed graph with labelled vertices 1..n. For each Warshall iteration show the adjacency matrix as a table with rows i and columns j, with 0/1 entries. Label the pivot vertex k for that iteration and show which row/column is used to update other entries.

Formulas

R^+ = ⋃_{k=1..n} R^k — R^+ is union of boolean powers; R^k = k-fold boolean product of adjacency matrices. Symbols: R^+ is transitive closure, R^k is k-step reachability. No SI units (boolean values). Note: Using k up to n ensures cycles returning to the same vertex (i to i) are captured; for i != j, k up to n-1 suffices.

R* = I ∪ R^+ — reflexive transitive closure; I is identity relation {(i,i)}. When implementing Warshall, obtain R* by setting mat[i][i] = true for all i before the loops (or by unioning I afterward).

R^{(k)}[i,j] := R^{(k-1)}[i,j] ∨ (R^{(k-1)}[i,k] ∧ R^{(k-1)}[k,j]) — Warshall update rule. Symbols: ∨ = boolean OR, ∧ = boolean AND.

Time complexity = O(n^3) — n is number of vertices; applies to Warshall algorithm.

For programmers: Warshall core nested loops (zero-based indexes) to remember: for k in 0..n-1: for i in 0..n-1: for j in 0..n-1: mat[i][j] = mat[i][j] or (mat[i][k] and mat[k][j])

Worked examples

Example 1 — Warshall trace on a small digraph

  • Graph: vertices 1=A, 2=B, 3=C, 4=D. Edges: 1→2, 2→3, 3→1, 3→4.
  • Initial adjacency matrix A (rows i, columns j): Row1: [0,1,0,0] Row2: [0,0,1,0] Row3: [1,0,0,1] Row4: [0,0,0,0]

Trace (use k = 1,2,3,4):

  • k=1: only vertex 3 had edge to 1, so update row 3 := row3 OR row1 = [1,0,0,1] OR [0,1,0,0] = [1,1,0,1]. Matrix becomes: [0,1,0,0] [0,0,1,0] [1,1,0,1] [0,0,0,0]

  • k=2: rows with col2 = 1 are rows 1 and 3. Row2 = [0,0,1,0]. Update row1 := row1 OR row2 = [0,1,0,0] OR [0,0,1,0] = [0,1,1,0]; row3 := row3 OR row2 = [1,1,0,1] OR [0,0,1,0] = [1,1,1,1]. Matrix: [0,1,1,0] [0,0,1,0] [1,1,1,1] [0,0,0,0]

  • k=3: column 3 has 1s in rows 1,2,3. Row3 = [1,1,1,1]. Update row1 := row1 OR row3 = [0,1,1,0] OR [1,1,1,1] = [1,1,1,1]; row2 := row2 OR row3 = [0,0,1,0] OR [1,1,1,1] = [1,1,1,1]; row3 stays [1,1,1,1]. Matrix: [1,1,1,1] [1,1,1,1] [1,1,1,1] [0,0,0,0]

  • k=4: row4 is all zeros, so no change. Final transitive closure matrix (R^+): rows 1..3 all [1,1,1,1], row4 [0,0,0,0].

Interpretation: vertices 1,2,3 are mutually reachable (strongly connected); each of them reaches 4; 4 reaches no one.

Example 2 — relation on {1,2,3}

  • Relation R = {(1,2),(2,3)}. Adjacency matrix A: [0,1,0] [0,0,1] [0,0,0]
  • Compute A^2 (boolean): row1·col3 = 1 via 1→2 and 2→3, so A^2 has (1,3) = 1; others zero. So A^2 = {(1,3)}.
  • A^3 = zero because no path of length 3 exists. So R^+ = A ∪ A^2 = {(1,2),(2,3),(1,3)}. R* = add reflexive pairs {(1,1),(2,2),(3,3)}.
  • This matches Warshall result if run on the same adjacency matrix.

Common mistakes

  • Updating entries in the wrong order (overwriting necessary values). Warshall uses current matrix values; using a separate copy per k or updating in place as above is correct because the algorithm's correctness relies on simultaneous view of R^{(k-1)} values, but in-place update with loops ordered k outermost works.
  • Forgetting to iterate k from 1..n (or 0..n-1 in zero-based indices) — stopping early may miss paths that use higher-numbered intermediate vertices.
  • Index confusion between rows (source) and columns (destination).

For your exam

Typical question forms and what full answers include:

  • Definitions: "Define transitive closure and adjacency matrix" — give formal set definitions and matrix form, state R^+ = ⋃ R^k.
  • Derivation/proof: "Prove Warshall's correctness" — give the inductive argument that after k iterations you allow intermediate vertices from {1..k} and conclude at k=n you get R^+.
  • Trace/run: "Run Warshall on given small graph" — show initial matrix, show matrices after each k with pivot k labelled, and final reachability matrix; interpret it in words and/or as set of ordered pairs.
  • Complexity: "Time and space complexity" — state O(n^3) time, O(n^2) space; justify from three nested loops and storing n×n matrix.
  • Short note: "Difference between reflexive closure, transitive closure and reflexive-transitive closure" — give brief definitions and set expressions.

Full-marks answers must be precise: label vertices, show matrices or pairs, explain each Warshall step or give a clear induction proof for correctness.

Quick check

  1. What is the boolean update rule used in Warshall's algorithm?
  2. What is the transitive closure R^+ of R = {(1,2),(2,3)} on {1,2,3}?
  3. What is the time complexity of Warshall's algorithm in terms of number of vertices n? Answers: 1) R[i,j] := R[i,j] ∨ (R[i,k] ∧ R[k,j]) for pivot k. 2) R^+ = {(1,2),(2,3),(1,3)}. 3) O(n^3).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?