Shortest path tree

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.

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.

Source: Wide Area Network Design by Robert S. Cahn


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Shortest path problem — A graph with 6 vertices and 7 edges In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. An example is… …   Wikipedia

  • Open Shortest Path First — (OSPF) is an adaptive routing protocol for Internet Protocol (IP) networks. It uses a link state routing algorithm and falls into the group of interior routing protocols, operating within a single autonomous system (AS). It is defined as OSPF… …   Wikipedia

  • Multicast Open Shortest Path First — MOSPF (Multicast open shortest path first) ist die Multicast Erweiterung zu OSPF (open shortest path first). MOSPF ermöglicht das Multicast Routing innerhalb einer OSPF Domain. Hierbei ist aber besonderes Augenmerk auf die Tatsache zu legen, dass …   Deutsch Wikipedia

  • Red-black tree — A red black tree is a type of self balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer who called them symmetric… …   Wikipedia

  • Spanning Tree Protocol — Internet protocol suite Application layer BGP DHCP DNS FTP HTTP …   Wikipedia

  • Reverse path forwarding — (RPF) is a technique used in modern routers for the purposes of ensuring loop free forwarding of multicast packets in multicast routing and to help prevent IP address spoofing in unicast routing. Contents 1 Multicast RPF 2 Unicast RPF (uRPF) 2.1 …   Wikipedia

  • Distributed minimum spanning tree — The distributed minimum spanning tree problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential… …   Wikipedia

  • Suffix tree — In computer science, a suffix tree (also called suffix trie, PAT tree or, in an earlier form, position tree) is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many… …   Wikipedia

  • Minimum spanning tree — The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length. Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all… …   Wikipedia

  • Decision-tree pruning — is traversing and utilization methods of Artificial Intelligence. They are used in many programs including maps with shortest route calculations, WebMD, Law sites, and Chess. The Sudoku puzzles can also benefit from an efficient solution search… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”