Warshall's Algorithm
Warshall's algorithm computes the transitive closure of a directed graph — determining if a path exists between every pair of vertices.
Introduction
Warshall's Algorithm, proposed by Stephen Warshall in 1962, computes the transitive closure of a directed graph. Given an adjacency matrix, it determines for every pair (i, j) whether vertex j is reachable from vertex i (directly or through any path). It is essentially the Boolean version of the Floyd-Warshall algorithm.
Problem Statement
Given a directed graph represented by an adjacency matrix A, compute a matrix D where D[i][j] = 1 if there is a path from vertex i to vertex j (directly or indirectly), and 0 otherwise.
Real World Applications
- → Reachability analysis in directed graphs
- → Database query optimization
- → Compiler design — computing dominators
- → Social network influence analysis
- → Dependency checking in build systems
Algorithm Explanation
Warshall's algorithm iterates over all intermediate vertices k. For each pair (i, j), it checks: can we reach j from i either directly (D[i][j]) OR by going through k (D[i][k] AND D[k][j])? If either is true, D[i][j] is set to 1. After processing all intermediate vertices, D[i][j] = 1 means j is reachable from i.
Step-by-Step Procedure
- 1 Initialize D = adjacency matrix of the graph.
- 2 For each intermediate vertex k from 1 to n:
- 3 For each source vertex i from 1 to n:
- 4 For each destination vertex j from 1 to n:
- 5 D[i][j] = D[i][j] OR (D[i][k] AND D[k][j])
- 6 After all iterations, D[i][j] = 1 indicates a path exists from i to j.
- 7 Print the transitive closure matrix.
Complete C Program
#include<stdio.h>
#include<stdlib.h>
#define MAX 10
int D[MAX][MAX], n;
void warshall() {
int i, j, k;
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
D[i][j] = D[i][j] || (D[i][k] && D[k][j]);
}
int main() {
int i, j;
printf("Enter the Number of Vertices: ");
scanf("%d", &n);
printf("Enter the Adjacency Matrix:\n");
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%d", &D[i][j]);
warshall();
printf("Transitive Closure Matrix:\n");
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++)
printf("%d\t", D[i][j]);
printf("\n");
}
return 0;
}Sample Input & Output
4
0 1 0 0
0 0 0 1
0 0 0 0
1 0 1 0Transitive Closure Matrix:
1 1 1 1
1 1 1 1
0 0 0 0
1 1 1 1Dry Run / Trace
4-vertex graph. Adjacency: 1→2, 2→4, 4→1, 4→3. k=1: D[2][2]=D[2][1]&&D[1][2]=0. D[4][2]=D[4][1]&&D[1][2]=1. k=2: D[1][4]=D[1][2]&&D[2][4]=1. D[4][4]=D[4][2]&&D[2][4]=1. k=3: No updates (D[i][3]=0 for i≠4). k=4: D[1][1]=D[1][4]&&D[4][1]=1. D[1][3]=D[1][4]&&D[4][3]=1. D[2][1]=1, etc. Final matrix shows all reachability.
Advantages & Disadvantages
✓ Advantages
- + Simple and elegant Boolean DP implementation
- + Computes complete reachability in one pass
- + Works for any directed graph
- + Easy to understand and implement
✗ Disadvantages
- − O(V³) time — not suitable for very large graphs
- − Only gives reachability (1/0), not actual paths or distances
- − O(V²) space for the matrix
Viva Questions & Answers
Q1. What is transitive closure?
A matrix T where T[i][j] = 1 if there exists a directed path from vertex i to vertex j (of any length), 0 otherwise.
Q2. How is Warshall's algorithm different from Floyd's?
Warshall's computes Boolean reachability (transitive closure) using OR/AND operations. Floyd's computes actual shortest distances using min/addition.
Q3. What does D[i][j] = D[i][j] || (D[i][k] && D[k][j]) mean?
Vertex j is reachable from i if: it was already reachable OR we can reach k from i AND reach j from k.
Q4. Can Warshall's algorithm detect strongly connected components?
Indirectly yes. If both D[i][j] = 1 and D[j][i] = 1, vertices i and j are in the same SCC.
Q5. What is the input to Warshall's algorithm?
The adjacency matrix of a directed graph, where D[i][j] = 1 if there is a direct edge from i to j.