Relations · step 8 of 13

Warshall’s transitive closure algorithm

Warshall’s algorithm computes the transitive closure of a relation in O(n³) without repeatedly squaring matrices. It loops over each vertex k as a permitted intermediate, and sets Mᵢⱼ = Mᵢⱼ ∨ (Mᵢₖ ∧ Mₖⱼ). After processing k = 1 … n, entry (i,j) is 1 exactly when some path from i to j exists using any vertices at all.

Practise warshall’s transitive closure algorithm free → All Relations subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Write the initial Boolean matrixM⁰ᵢⱼ = 1 iff (i,j) ∈ R. Label rows and columns with the vertex order you will use for k.
Loop on the intermediate vertex kFor k = 1, then 2, and so on. The outer loop is over k — putting it inside is the classic implementation bug.
Update every (i,j) in that roundSet Mᵢⱼ to 1 whenever Mᵢₖ = 1 and Mₖⱼ = 1. Practically: look at column k and row k, and fill in the rectangle of their intersections.
Carry the updated matrix forwardRound k + 1 uses the matrix produced by round k, including everything just added. That is why one pass per vertex suffices.

Worked example

Run Warshall on {1,2,3} with R = {(1,2),(2,3)}.

M⁰: 1→2 and 2→3 only.
k = 1: any i→1 and 1→j? Nothing points to 1, so no change.
k = 2: rows pointing to 2: row 1. Columns from 2: column 3. So set M₁₃ = 1.
k = 3: nothing leaves 3, so no change. Final matrix has 1→2, 2→3, 1→3.

Answer. R⁺ = {(1,2),(2,3),(1,3)}, obtained in three rounds with no iteration to a fixed point.

Where marks get dropped

These are the specific errors that cost credit on warshall’s transitive closure algorithm questions — QED's rubric penalises each of them separately.

Nesting the loops in the wrong order. k must be the outermost loop; making it innermost computes something that is not the closure.
Using the original matrix in later rounds instead of the updated one. Updates must accumulate.
Expecting the diagonal to fill in. Warshall gives the transitive closure — (i,i) appears only if i lies on a cycle.

Practise this until it is automatic

Unlimited fresh questions

QED generates new warshall’s transitive closure algorithm problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Relations mastery is tracked so you know when this is exam-ready.

Warshall’s transitive closure algorithm — frequently asked questions

Why is Warshall O(n³)?

Three nested loops over n vertices, each doing constant work. Repeated Boolean matrix squaring costs O(n³ log n), so Warshall is genuinely better as well as simpler.

What is the connection to Floyd–Warshall?

The same loop structure. Replace the Boolean OR/AND with min and + on edge weights and you get all-pairs shortest paths instead of reachability.

Can I use it for the reflexive-transitive closure?

Yes — initialise the diagonal to 1 before starting, and the output is R*.

The rest of Relations

Properties of relations, composition, and representations. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make warshall’s transitive closure algorithm exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →