Shortest-Path Tree

A Shortest-Path Tree is a [[]] that ...

• See: Breadth-First Search, Connected Graph, Undirected Graph, Graph Theory, Spanning Tree, Shortest Path, Dijkstra's Algorithm, Bellman–Ford Algorithm, Minimum Spanning Tree.

---

---

References

2017

• (Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/shortest-path_tree Retrieved:2017-12-30.
  • Given a connected, undirected graph G, a shortest-path tree rooted at vertex v is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G.

    In connected graphs where shortest paths are well-defined (i.e. where there are no negative-length cycles), we may construct a shortest-path tree using the following algorithm:

    1. Compute dist(u), the shortest-path distance from root v to vertex u in G using Dijkstra's algorithm or Bellman–Ford algorithm.
    2. For all non-root vertices u, we can assign to u a parent vertex p_u such that p_u is connected to u, and that dist(p_u) + edge_dist(p_u,u) = dist(u). In case multiple choices for p_u exist, choose p_u for which there exists a shortest path from v to p_u with as few edges as possible; this tie-breaking rule is needed to prevent loops when there exist zero-length cycles.
    3. Construct the shortest-path tree using the edges between each node and its parent.
  • The above algorithm guarantees the existence of shortest-path trees. Like minimum spanning trees, shortest-path trees in general are not unique.

    In graphs for which all edges weights equal one, shortest path trees coincide with breadth-first search trees.

    In graphs that have negative cycles, the set of shortest simple paths from v to all other vertices do not necessarily form a tree.

---