Before step k
M⁽ᵏ⁻¹⁾[i,j] = 1 means a path already exists using only earlier intermediate vertices.
Warshall Algorithm Reachability Matrix Calculator
Enter an adjacency matrix
Positive reachability puts 1 on the diagonal only for a self-loop or nonempty cycle.
Private by design: the matrix and labels stay on this device. They are not uploaded, saved, or added to the page URL.
Advertisement
How Warshall's algorithm calculates reachability
Let M⁽⁰⁾ be the adjacency matrix, with the diagonal initialized according to the selected convention. At step k, vertex k becomes an allowed intermediate. For every ordered pair (i,j):
M⁽ᵏ⁾[i,j] = M⁽ᵏ⁻¹⁾[i,j] ∨ (M⁽ᵏ⁻¹⁾[i,k] ∧ M⁽ᵏ⁻¹⁾[k,j])
Through vertex k
The Boolean AND is 1 when i can reach k and k can reach j.
After all n steps
M⁽ⁿ⁾ is the reachability matrix. Each 1 represents an allowed directed path.
Three nested loops give Θ(n³) Boolean checks and the matrix uses Θ(n²) working space. This page retains intermediate matrices for the step explorer, using Θ(n³) bytes in the worst case under its 120-vertex limit.
Positive versus reflexive reachability
Positive paths: length ≥ 1
This is the transitive closure A⁺. A vertex reaches itself only through an entered self-loop or a nonempty directed cycle.
Reflexive paths: length ≥ 0
This is the reflexive-transitive closure A*. The length-zero path makes every vertex reachable from itself, so the starting diagonal is set to 1.
Directed interpretation: row i is the source and column j is the destination. A 1 at (i,j) does not imply a 1 at (j,i).
Warshall algorithm example
For edges A→B, B→C, C→D, and D→B, using B as an intermediate makes A→C reachable. Later steps discover A→D. The cycle B→C→D→B makes B, C, and D positively reachable from themselves.
| Source | Positively reachable vertices | Why |
|---|---|---|
| A | B, C, D | Follow the chain from A into the cycle. |
| B | B, C, D | B belongs to the B–C–D cycle. |
| C | B, C, D | C belongs to the B–C–D cycle. |
| D | B, C, D | D belongs to the B–C–D cycle. |
Input rules, assumptions, and limits
Enter one matrix row per line and separate entries with spaces or commas. Every entry must be exactly 0 or 1, and the matrix must be square. Blank lines are ignored. The calculator treats rows as source vertices and columns as destination vertices.
Optional labels are case-sensitive and must be unique. Separate them with commas, semicolons, or line breaks. Their count must match the matrix size; otherwise the calculator uses v1, v2, …, vn. Labels may be up to 80 characters.
The calculator accepts matrices from 1 × 1 through 120 × 120. This limit bounds the cubic calculation, step history, and rendered table so an accidental extreme input does not make the page unresponsive.
The definition of transitive closure follows the NIST Dictionary of Algorithms and Data Structures. The recurrence shown above is the standard Boolean dynamic-programming form of Warshall's algorithm.
Calculation note: focused tests cover chains, cycles, disconnected vertices, reflexive mode, size limits, invalid matrices, and formatted outputs. Last reviewed: .
Warshall algorithm FAQ
What does a reachability matrix show?
Entry (i,j) is 1 when the directed graph contains an allowed path from vertex i to vertex j. Otherwise it is 0.
How does Warshall's algorithm work?
It considers each vertex k as an allowed intermediate in turn. Entry (i,j) becomes 1 when it was already 1 or both (i,k) and (k,j) are 1.
Should the reachability matrix diagonal contain 1s?
It depends on the convention. Positive reachability needs a self-loop or nonempty cycle. Reflexive reachability allows a zero-edge path, so every diagonal entry is 1.
Is Warshall's algorithm the same as Floyd–Warshall?
They use the same three-loop dynamic-programming pattern. Warshall combines Boolean reachability values; Floyd–Warshall combines path distances to solve the all-pairs shortest-path problem.
What is the time complexity of Warshall's algorithm?
The standard algorithm uses Θ(n³) time and Θ(n²) working space for n vertices.
Can the graph be disconnected?
Yes. Unreachable source–destination pairs remain 0, including rows for isolated vertices except diagonal entries in reflexive mode.
Does this calculator upload my matrix?
No. Parsing, calculation, copying, and CSV creation happen locally in your browser. The tool does not transmit or save the matrix.