Transitive Closure

In this section, we look at two well-known algorithms: Warshall’s algorithm for computing the transitive closure of a directed graph and Floyd’s algorithm for the all-pairs shortest-paths problem. These algorithms are based on essentially the same idea: exploit a relationship between a problem and its simpler rather than smaller version. Warshall and Floyd published their algorithms without mentioning dynamic programming. Nevertheless, the algorithms certainly have a dynamic programming flavor and have come to be considered applications of this technique.