Overview
Warshall's algorithm updates a reachability matrix so entry (i, j) becomes true when vertex j can be reached from vertex i through any allowed intermediate vertex.
CoreSource checked
Warshall's Algorithm
Computes transitive closure by repeatedly allowing each vertex as an intermediate step.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Transitive Closure
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
transitive closuregraph traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when all-pairs reachability is needed and O(n^3) work is acceptable.
- Use when a dense matrix representation is simpler than repeated graph searches.
When Not to Use
- Avoid for very large sparse graphs where repeated DFS or BFS is cheaper.
- Avoid when weighted shortest paths are needed instead of Boolean reachability.
What It Does
- Stores reachability in a Boolean matrix
- Considers each vertex as a possible intermediate
- Updates all pairs that become reachable through that vertex
Use Cases
- Transitive closure of directed graphs
- Reachability queries on small to medium dense graphs
- Prerequisite or dependency closure checks
Inputs
- Transitive Closure input instance for transitive closure
- Configuration parameters controlling transitive closure
Outputs
- Computed transitive closure solution produced by Warshall's Algorithm
- Diagnostic state over transitive closure and graph traversal
Pseudocode
- 1.Initialize reachable[i][j] from graph edges
- 2.Optionally set reachable[i][i] to true
- 3.For each intermediate vertex k
- 4.For each source i and target j
- 5.Set reachable[i][j] if reachable[i][k] and reachable[k][j]
- 6.Return the reachability matrix
Canonical Example
- Input
- edges A->B and B->C
- Output
- A reaches B, B reaches C, and A reaches C
- Explanation
- When B becomes an allowed intermediate, reachability from A to C is added.
Implementation Notes
- Use the loop order k, i, j so k is the newly allowed intermediate.
- Decide whether every vertex is reachable from itself before initializing the matrix.
- Test a chain A->B->C to verify that A reaches C after the update.
Common Pitfalls
- Forgetting to initialize direct edges and self-reachability consistently.
- Using the wrong loop order can break the dynamic-programming invariant.
- Confusing transitive closure with transitive reduction.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow updating reachability through each intermediate vertex in turn on a small transitive closure example.
Step 1 of 6: Initialize reachable[i][j] from graph edges
graph-traversal-mechanismNotes
Warshall's algorithm is the Boolean reachability version of the Floyd-Warshall dynamic-programming pattern.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Warshall's Algorithm's algorithm family, complexity framing, and standard implementation concepts.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Warshall's Algorithm in the graph, flow, matching, and combinatorial optimization benchmark area.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toTransitive Reduction
Warshall computes all implied reachability; transitive reduction removes edges implied by other paths.
Conceptual neighborFloyd-Warshall
Both use the same intermediate-vertex dynamic-programming loop structure.
Related Algorithms
Tags
GraphTraversal