Warshall's Algorithm

Warshall's algorithm is a dynamic programming method for computing the transitive closure of a directed graph or binary relation, determining for every pair of vertices whether a path exists between them regardless of length. It works by considering each vertex in turn as a possible intermediate stop and updating a boolean reachability matrix so that reachability through the current intermediate vertex is folded into the record for every pair, continuing until every vertex has served as an intermediate and the matrix reflects full transitive closure. Stephen Warshall published the algorithm in January 1962 in a paper titled "A Theorem on Boolean Matrices," working with logical conjunction and disjunction rather than arithmetic; Robert Floyd published a closely related algorithm the same year that applies the identical recurrence to weighted graphs using ordinary addition and minimum instead of the boolean operations, extending the same technique to compute shortest paths rather than mere reachability. Because of this shared structure, the shortest path version is now generally known as the Floyd-Warshall algorithm, while Warshall's own boolean version remains the standard reference for computing transitive closure directly.