Warshall's algorithm (idea)

(Put another way: if a relation R is regarded as the set of possible steps we can take in some literal or non-literal sense, then R⁺ is the set of journeys we can make: it relates all pairs such that some path of steps leads from the first to the second.)

One way to compute it, in the finite case, is by iterating over the members of the domain, and in each step of the computation compute R⁺ limited to the members considered thus far. This is known as Floyd's algorithm.

In A theorem on boolean matrices, Stephen Warshall's paper in the Journal of the ACM, 9(1):11-12, 1962, it was observed that when the incidence matrix of the relation is represented as a set of bit vectors, this algorithm is a matrix multiplication at each step. If this is a constant time operation, the total complexity of transitive closure becomes quadratic.

Warshall's algorithm can only be applied if the number of domain elements is limited to the size of your bit vectors; that is, the word size of your computer, or the vector size on specially built array processors that were popular for a while.

If the size of the domain is unknown in advance, but the relation is still dense, it's still a good idea to use the fast algorithms for matrix multiplication. When the relation is sparse, it becomes too wasteful to represent it as an incidence matrix, and one has to resort to Floyd's algorithm.

The history behind these names is rather odd, if you ask me: first, Warshall published his paper in which his main contribution is to note that transitive closure computation can be regarded as iterated matrix multiplication; then, Floyd published a short note to state the three-nested algorithm that we all know and love, referring to Warshall's paper as the source of his observation; it's that algorithm that is known as Floyd's and sometimes as Warshall's, while the other, asymptotically faster algorithms that Warshall's observation allows don't appear to have specific names.