the importance of the floyd-warshall algorithm is that it is much easier to implement than dfsand much faster in practice because there are relatively few low-level operations hidden within the asymptotic notation the algorithm is particularly well suited for the use of an adjacency matrixas single bit can be used to designate the reachability modeled as an edge (uvin the transitive closure howevernote that repeated calls to dfs results in better asymptotic performance when the graph is sparse and represented using an adjacency list or adjacency map in that casea single dfs runs in ( mtimeand so the transitive closure can be computed in ( nmtimewhich is preferable to ( python implementation we conclude with python implementation of the floyd-warshall algorithmas presented in code fragment although the original algorithm is described we create single copy of the using series of directed graphs original graph (using the deepcopy method of python' copy moduleand then repeatedly add new edges to the closure as we progress through rounds of the floydwarshall algorithm the algorithm requires canonical numbering of the graph' verticesthereforewe create list of the vertices in the closure graphand subsequently index that list for our order within the outermost loopwe must consider all pairs and finallywe optimize by only iterating through all values of after we have verified that has been chosen such that (vi vk exists in the current version of our closure def floyd warshall( ) """return new graph that is the transitive closure of "" closure deepcopy(gimported from copy module verts list(closure vertices)make indexable list len(verts for in range( ) for in range( ) verify that edge ( ,kexists in the partial closure if ! and closure get edge(verts[ ],verts[ ]is not none for in range( ) verify that edge ( ,jexists in the partial closure if ! ! and closure get edge(verts[ ],verts[ ]is not none if ( ,jnot yet includedadd it to the closure if closure get edge(verts[ ],verts[ ]is none closure insert edge(verts[ ],verts[ ] return closure code fragment python implementation of the floyd-warshall algorithm