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).