A shortest path tree, in graph theory, is a subgraph of a given (possibly weighted) graph constructed so that the distance between a selected root node and all other nodes is minimal. It is a tree because if there are two paths between the root node and some vertex v (i.e. a cycle), we can delete the last edge of the longer path without increasing the distance from the root node to any node in the subgraph.



If every pair of nodes in the graph has a unique shortest path between them, then the shortest path tree is unique. This is because if a particular path from the root to some vertex is minimal, then any part of that path (from node u to node v) is a minimal path between these two nodes.



In graphs with no negative distances, Dijkstra s algorithm computes the shortest path tree, from a given vertex. In graphs with possibly negative distances, the Bellman-Ford algorithm can be used instead.