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.
Articles by others on the same topic
A **shortest-path tree** is a type of data structure used in graph theory that represents the shortest paths from a single source vertex to all other vertices in a weighted graph. The shortest-path tree is a subtree of the graph and satisfies the property that for any vertex in the tree, the path from the source vertex to that vertex is the shortest possible path in the graph. ### Key Characteristics: 1. **Source Vertex**: The node from which the shortest paths originate.