DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).
Transitive Closure and Warshall's Algorithm
Answering "can you reach B from A at all, through ANY path?" — for every pair, all at once.
The transitive closure of a graph tells you, for every pair of vertices, whether ANY path exists between them (not necessarily direct) — useful for questions like "is this website reachable from that one through any chain of links?"
Warshall's Algorithm — the core idea:
Start with the adjacency matrix (direct edges only).
For each intermediate vertex k (from 1 to n):
For each pair (i,j):
If path[i][k]=1 AND path[k][j]=1, set path[i][j]=1
(meaning: if i can reach k, and k can reach j, then i can reach j)
After considering ALL vertices as possible intermediates,
the matrix shows every pair's full reachability.
💡 Practice a full worked Warshall's algorithm numerical on a small 4-5 vertex graph, showing the matrix updating after considering each intermediate vertex k — this exact step-by-step format is how it's graded.
The loop order, which is the whole algorithm
Warshall looks like three nested loops that could go in any order. They cannot. k must be the outermost loop, and getting this wrong produces a wrong answer that still looks plausible.
for k = 1 to n: ← intermediate vertex, MUST be outermost
for i = 1 to n:
for j = 1 to n:
path[i][j] = path[i][j] OR (path[i][k] AND path[k][j])
The reason is what each pass guarantees. After the pass for a given k, the matrix records every path using only vertices 1..k as intermediates. Each new k extends that set by one. Put i or j outside instead and you finalise some pairs before all their possible intermediates have been considered, so genuine paths get missed.
💡 The exam question is often "why must k be the outer loop?" — the answer is that the algorithm builds up allowable intermediate vertices one at a time, and every pair must be re-examined after each new one is admitted.
Cost, and when to use it
Three nested loops over n vertices give O(n³) time and O(n²) space, regardless of how many edges the graph has. That fixed cost is the deciding factor.
Running a traversal from each vertex costs O(V·(V+E)), which on a sparse graph is considerably cheaper than n³. So Warshall wins on dense graphs and when you want all pairs at once in a simple matrix form; repeated BFS wins when the graph is sparse or you need only a few sources.
💡 Warshall's algorithm for reachability and Floyd's for shortest paths are the same triple loop with one line changed: OR/AND becomes min/plus. Recognising them as one algorithm halves what there is to remember.
Syllabus points
Transitive closure of a graph
Warshall's algorithm (numerical)
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.