Past exam question: 2075 Baisakh (Back), Q10
Open in the Padhaiko appQuestion
Write an algorithm for Warshall's algorithm and illustrate with an example.
Solution
Warshall's Algorithm for Transitive Closure: Given an adjacency matrix of a directed graph , Warshall's algorithm computes the reachability matrix in time:
Algorithm WARSHALL(A, n):
1. R = copy of A
2. For k = 0 to n - 1:
For i = 0 to n - 1:
For j = 0 to n - 1:
R[i][j] = R[i][j] OR (R[i][k] AND R[k][j])
3. Return RWorked Example on a 3-Vertex Directed Graph (0 -> 1, 1 -> 2): Initial adjacency matrix :
- (via vertex 0): Column 0 has no
1s . - (via vertex 1): Row 0 has
1in column 1, and row 1 has1in column 2 set :
- (via vertex 2): Row 2 is all zeros .
Answer:
Warshall's algorithm updates for each intermediate vertex in time, discovering indirect paths such as ().