reconstructing the shortest-path tree our pseudo-code description of dijkstra' algorithm in code fragment and our implementation in code fragment computes the value [ ]for each vertex vthat is the length of the shortest path from the source vertex to howeverthose forms of the algorithm do not explicitly compute the actual paths that achieve those distances the collection of all shortest paths emanating from source can be compactly represented by what is known as the shortest-path tree the paths form rooted tree because if shortest path from to passes through an intermediate vertex uit must begin with shortest path from to in this sectionwe demonstrate that the shortest-path tree rooted at source can be reconstructed in ( mtimegiven the set of [vvalues produced by dijkstra' algorithm using as the source as we did when representing the dfs and bfs treeswe will map each vertex  to parent (possiblyu )such that is the vertex immediately before on shortest path from to if is the vertex just before on the shortest path from to vit must be that [uw(uvd[vconverselyif the above equation is satisfiedthen the shortest path from to ufollowed by the edge (uvis shortest path to our implementation in code fragment reconstructs the tree based on this logictesting all incoming edges to each vertex vlooking for (uvthat satisfies the key equation the running time is ( )as we consider each vertex and all incoming edges to those vertices (see proposition def shortest path tree(gsd) """reconstruct shortest-path tree rooted at vertex sgiven distance map return tree as map from each reachable vertex (other than sto the edge =( ,vthat is used to reach from its parent in the tree "" tree for in if is not sconsider incoming edges for in incident edges(vfalse) opposite( wgt element if [ = [uwgt tree[ve edge is used to reach return tree code fragment python function that reconstructs the shortest pathsbased on knowledge of the single-source distances