of by incrementally computing series of digraphs where for this description is actually an example of an algorithmic design pattern known as dynamic programmingwhich is discussed in more detail in section from the description and analysis above we may immediately derive the following proposition proposition let be digraph with verticesand let be represented by data structure that supports lookup and update of adjacency information in ( time then the floyd-warshall algorithm computes the transitive closure in ( time of we illustrate an example run of the floyd-warshall algorithm in figure figure sequence of digraphs computed by the floyd-warshall algorithm(ainitial digraph and numbering of the vertices(bdigraph ( (dif (edigraph (fnote that has the edges ( , and ( )but not the edge (vivj)in the drawing of digraph we show