Warshall’s Algorithm Computes the transitive closure of a relation, i.e., existence of all nontrivial paths in a digraph.

The transitive closure of a directed graph with n vertices can be defined as the n × n boolean matrix in which the element in the ith row and the jth column is 1 if there exists a nontrivial path (i.e., directed path of a positive length) from the ith vertex to the jth vertex; otherwise, it is 0.