table continued we can use warshall' algorithm to change the adjacency matrix into the transitive closure of the graph this algorithm does lot in few lines of code it' based on simple ideaif you can get from vertex to vertex mand you can get from to nthen you can get from to we've derived two-step path from two one-step paths the adjacency matrix shows all possible one-step pathsso it' good starting place to apply this rule you might wonder if this algorithm can find paths of more than two edges after allthe rule only talks about combining two one-edge paths into one two-edge path as it turns outthe algorithm will build on previously discovered multi-edge paths to create paths of arbitrary length the implementation we will describe guarantees this resultbut proof is beyond the scope of this book here' how it works we'll use table as an example we're going to examine every cell in the adjacency matrixone row at time row we start with row there' nothing in columns and bbut there' at column cso we stop there now the at this location says there is path from to if we knew there was path from some vertex to athen we would know there was path from to where are the edges (if anythat end at athey're in column so we examine all the cells in column in table there' only one in column aat row it says there' an edge from to so we know there' an edge from to aand another (the one we started withfrom to from this we infer that we can get from to in two steps you can verify this is true by looking at the graph in figure to record this resultwe put at the intersection of row and column the result is shown in figure the remaining cells of row are blank rows bcand we go to row the first cellat column ahas indicating an edge from to are there any edges that end at bwe look in column bbut it' emptyso we know that none of the we find in row will result in finding longer paths because no edges end at