### Transitive Closure

Floyd's algorithm finds the cost of the least cost path (or the path
itself) between every pair of vertices.

Often we only want to know if there is a path between
any two vertices (and ignore costs).

Warshall's algorithm is a specialized (but earlier)
version of Floyd's algorithm that solves this problem,
called the *transitive closure* of a graph.

Given a directed graph G = (V,E),
represented by an adjacency matrix A[i,j],
where A[i,j] = 1 if (i,j) is in E,
compute the matrix P, where P[i,j] is 1 if there is a path
of length greater than or equal to 1 from i to j.

### Warshall's Algorithm

**
Warshall (int N, bmatrix &A, bmatrix &P)
{
int i,j,k;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
/* There's a path if there's an edge */
P[i][j] = A[i][j];
for (k = 0; k < N; k++)
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (! P[i][j])
P[i][j] = P[i][k] && P[k][j];
} /* Warshall */
**

Clearly the algorithm is O(N^3).