a shortest-path tree

When you solve the single-source problem, you do not just get a list of distances — you get a beautiful structure for free. Collect, for each vertex, the last road on its cheapest route from the source. Those chosen roads link up into a tree rooted at the source, and the unique path from the root to any vertex inside this tree is a shortest path to it. One compact tree encodes the best route to everywhere at once.

Build it from the predecessor pointers that relaxation leaves behind: whenever relaxing edge (u, v) lowers d[v], you record pred[v] = u. At the end, for each reachable vertex v (other than the source) the edge (pred[v], v) is its tree edge. These edges form a tree because every vertex has exactly one predecessor and following predecessors always leads back toward the source without cycles. Walking pred pointers from v back to s and reversing gives a shortest path to v. The key fact is optimal substructure: any subpath of a shortest path is itself a shortest path, so a single tree can simultaneously hold a shortest path to every vertex — shared prefixes are simply shared branches of the tree.

The shortest-path tree is the actual deliverable of routing: GPS gives you a route, not just a mileage number, and that route is a root-to-vertex path in this tree. A subtle point worth flagging: the tree is generally NOT unique — when two routes tie in cost, different tie-breaking yields different valid trees, all equally optimal. Also note this tree is about distances FROM one source and is unrelated to a minimum spanning tree, which minimizes total edge weight and ignores any source; the two solve different problems and usually look different.