Published by Dimitris Kougioumtzis · Updated
Mark whether every source can reach every destination, including the zero-edge path to itself.
Combine Boolean reachability through each possible intermediate vertex until every reachable pair is recorded.
When to use Warshall transitive closure
All-pairs directed reachability.
Choosing an alternative
Floyd-Warshall minimizes route costs rather than combining Boolean paths.
Worked example: input and state changes
Example input
0,1,4; 0,2,2; 2,1,1; 1,3,5; 2,3,8; 3,4,2
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Reachability matrix: 1 means reachable; diagonal includes empty paths.
State at this checkpoint
{ "values": [ 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1 ], "active": [], "kind": "matrix", "columns": 5 }Step 1: Reach 3 from 0 through 1.
State at this checkpoint
{ "values": [ 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1 ], "active": [ 3 ], "kind": "matrix", "columns": 5 }Step 3: Reach 4 from 1 through 3.
State at this checkpoint
{ "values": [ 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1 ], "active": [ 9 ], "kind": "matrix", "columns": 5 }Step 4: Reach 4 from 2 through 3.
State at this checkpoint
{ "values": [ 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1 ], "active": [ 14 ], "kind": "matrix", "columns": 5 }Step 5: Transitive closure complete.
State at this checkpoint
{ "values": [ 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1 ], "active": [], "kind": "matrix", "columns": 5 }
Expected final state
Transitive closure complete.
Complexity and input bounds
Family: Graphs. Time complexity: O(V³).
Space complexity: O(V squared) reachability table.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Directed edges as source,target,weight; separated by semicolons. Nodes 0–7, positive weights 1–99. Start node is 0.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
The diagonal includes zero-length self-reachability; the table does not count paths or give costs.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | // Directed edge arrays from, to, weight; nodes 0..vertices-1; source 0. Up to 8 vertices, 16 edges. Allocate output with at least 256 integers. Ignores weights. Writes reflexive transitive closure as a row-major 0/1 matrix. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(from, to, weight, edges, vertices, output) { for (let i = 0; i < vertices * vertices; i++) { output[i] = 0; } for (let i = 0; i < vertices; i++) { output[i * vertices + i] = 1; } for (let i = 0; i < edges; i++) { output[from[i] * vertices + to[i]] = 1; } for (let k = 0; k < vertices; k++) { for (let i = 0; i < vertices; i++) { for (let j = 0; j < vertices; j++) { if (output[i * vertices + k] == 1 && output[k * vertices + j] == 1) { output[i * vertices + j] = 1; } } } } return 0; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- A Theorem on Boolean Matrices
Stephen Warshall (1962). Research paper.