Warshall’s Algorithm

Warshall's algorithm is a classic method for finding the transitive closure of a directed graph efficiently. It works by iteratively updating a boolean matrix based on the presence of paths between vertices. 

Warshall’s algorithm after Stephen Warshall, who discovered it [War62]. It is convenient to assume that the digraph’s vertices and hence the rows and columns of the adjacency matrix are numbered from 1 to n. Warshall’s algorithm constructs the transitive closure through a series of n × n boolean matrices:

R(0), . . . , R(k−1), R(k), . . . R(n). 

Each of these matrices provides certain information about directed paths in the digraph. Specifically, the element r(k) in the ith row and jth column of matrix ij R(k) (i,j=1,2,...,n,k=0,1,...,n)is equal to1 if and only if there exists a directed path of a positive length from the ith vertex to the jth vertex with each intermediate vertex, if any, numbered not higher than k. Thus, the series starts with R(0), which does not allow any intermediate vertices in its paths; hence, R(0) is nothing other than the adjacency matrix of the digraph. (Recall that the adjacency matrix contains the information about one-edge paths, i.e., paths with no intermediate vertices.) R(1) contains the information about paths that can use the first vertex as intermediate; thus, with more freedom, so to speak, it may contain more 1’s than R(0). In general, each subsequent matrix in series (8.9) has one more vertex to use as intermediate for its paths than its predecessor and hence may, but does not have to, contain more 1’s. The last matrix in the series, R(n), reflects paths that can use all n vertices of the digraph as intermediate and hence is nothing other than the digraph’s transitive closure.

The central point of the algorithm is that we can compute all the elements of each matrix R(k) from its immediate predecessor R(k−1) in series (8.9). Let r(k), ij the element in the ith row and jth column of matrix R(k), be equal to 1. This means that there exists a path from the ith vertex vi to the jth vertex vj with each intermediate vertex numbered not higher than k:

Thus, we have the following formula for generating the elements of matrix R(k) from the elements of matrix R(k−1):

Here's a step-by-step explanation of Warshall's algorithm:

Initialization: Start with the given adjacency matrix A of the directed graph.

Iteration: Perform n iterations (where n is the number of vertices in the graph), updating the matrix in each iteration.

Update Rule: At each iteration k, update the matrix T as follows:

• For each pair of vertices (i,j), if there is no direct edge from i to j (i.e., A[i][j]=0), but there exists a path from i to j passing through vertex k (i.e., both T[i][k]=1 and T[k][j]=1), then set T[i][j]=1.

This step essentially checks if there's a path from i to j through vertex k and updates the transitive closure matrix accordingly.

Termination: After n iterations, the resulting matrix T represents the transitive closure of the graph.

Warshall’s Algorithm to find transitive closure of a graph:

ALGORITHM Warshall(A[1..n, 1..n])
// Implements Warshall’s algorithm for computing the transitive closure
// Input: The adjacency matrix A of a digraph with n vertices
// Output: The transitive closure of the digraph

R(0) ← A
for k ← 1 to n do
    for i ← 1 to n do
        for j ← 1 to n do
            R(k)[i, j] ← R(k - 1)[i, j] or (R(k - 1)[i, k] and R(k - 1)[k, j])
return R(n)

Find transitive closure of graph using Warshall's algorithm: