Shortest path tree
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.
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.
A known problem with using shortest path tree in network design is cost, reliability and bandwidth
required at the central node.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, 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
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
computes the shortest path tree, from a given vertex. In graphs with possibly negative distances, the Bellman-Ford algorithm
Bellman-Ford algorithm
The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph.For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem....
can be used instead.
A known problem with using shortest path tree in network design is cost, reliability and bandwidth
Bandwidth (computing)
In computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
required at the central node.