/*compute all-shortest paths contains the adjacency matrix with ai ] presumed to be zero contains the values of the shortest path vertices are numbered starting at all arrays have equal dimension negative cycle exists if di ] is set to negative value actual path can be computed using path]not_a_vertex is - *void allpairsconst matrix amatrix dmatrix path int numrows)/initialize and path forint ++ forint ++ di ] ai ] ]pathi ] not_a_vertexforint ++ /consider each vertex as an intermediate forint ++ forint ++ ifdi ] dk ] di ] /update shortest path di ] di ] dk ] ]pathi ] kfigure all-pairs shortest path because the kth stage depends only on the ( )th stageit appears that only two |vx |vmatrices need to be maintained howeverusing as an intermediate vertex on path that starts or finishes with does not improve the result unless there is negative cycle thusonly one matrix is necessarybecause dk- , , dk, , and dk- , , dk, , which implies that none of the terms on the right change values and need to be saved this observation leads to the simple program in figure which numbers vertices starting at zero to conform with ++' conventions