We look at Warshall algorithm for transitive closure.  In a directed or undirected graph, we ask if there is a path from node I to mode j. That is transitive closure. As we may recall from previous posts, we represent a graph with an adjacency matrix.  For a graph with N nodes, an adjacency matrix answers the question whether there is an edge between node I and J. For both directed and undirected graphs a value of 0 in the adjacency matrix indicates there is no edge. A transitive closure finds whether there is a path between node I and j. Here we could apply a brute force method of enumerating N ^2 pairs of vertices and try to find a path for each pair. Fortunately, Warshall algorithm answers that better by using dynamic programming particularly the step of saving the previously found paths so that we can efficiently compute the transitive closure. Here for node I and J  we ask if there is a path through node 1. Next we ask if there's a path through node 1 and 2. Next we ask if there's a path through node 1,2 and 3 and so on.
Warshalls' algorithm has applications in network routing and reachability problems. Its also used to eliminate states.
The algorithm is elaborated as follows:
Algorithm Warshall(A[1..n, 1..n])
{
   R-0  is initialized with the adjacency matrix ; // R-0 is the node to itself.
   for k = 1  to n do
      for i = 1 to n do
        for j = 1 to n do
            R-k[i, j] = R-(k-1) [i, j] OR
                             (R-(k-1) [i, k] AND  R-(k-1) [k,j])
                             // path from i to k thru 1,2 .. k -1
                            // and path from k to j thru 1,2, .. k-1
  return R-(n)
}