Shortest path tree
From Wikipedia, the free encyclopedia
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.
It is unique because if a certain 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.
Dijkstra's algorithm computes the shortest path tree. Its applications extend to graph theory and network design.
A known problem with using shortest path tree in network design is cost, reliability and bandwidth required at the central node.
Source: Wide Area Network Design by Robert S. Cahn