Shortest path tree

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

This mathematics-related article is a stub. You can help Wikipedia by expanding it.