graph algorithms proposition suggests simple algorithm for computing the transitive clothat is based on the series of rounds to compute each this algorithm sure of is known as the floyd-warshall algorithmand its pseudo-code is given in code fragment we illustrate an example run of the floyd-warshall algorithm in figure algorithm floydwarshall( )with vertices inputa directed graph of outputthe transitive closure let vn be an arbitrary numbering of the vertices of  for to do -  for all ij in { nwith  and ij  do - then if both edges (vi vk and (vk are in (if it is not already presentadd edge (vi to return gn code fragment pseudo-code for the floyd-warshall algorithm this algoof by incrementally computing series rithm computes the transitive closure for of directed graphs from this pseudo-codewe can easily analyze the running time of the floydwarshall algorithm assuming that the data structure representing supports methods get edge and insert edge in ( time the main loop is executed times and the inner loop considers each of ( pairs of verticesperforming constant-time computation for each one thusthe total running time of the floyd-warshall algorithm is ( from the description and analysis above we may immediately derive the following proposition be directed graph with verticesand let be repreproposition let sented by data structure that supports lookup and update of adjacency information in ( time then the floyd-warshall algorithm computes the transitive closure of in ( time performance of the floyd-warshall algorithm asymptoticallythe ( running time of the floyd-warshall algorithm is no better than that achieved by repeatedly running dfsonce from each vertexto compute the reachability howeverthe floyd-warshall algorithm matches the asymptotic bounds of the repeated dfs when graph is denseor when graph is sparse but represented as an adjacency matrix (see exercise -