= Shortest-path tree
A <shortest-path tree> rooted at a source vertex is a <spanning tree> whose unique tree route from the source to every <vertex> solves the <shortest path problem> in the original <weighted graph>. <Dijkstra's algorithm> constructs one for a finite connected <graph> with nonnegative <edge> lengths, recording a predecessor whenever a distance improves. It need not be a <minimum spanning tree>: one minimizes each source-route length, the other the total weight of the tree's edges.
Back to article page
