Nejkratší cesta strom - Shortest-path tree - Wikipedia

Vzhledem k připojeno, neorientovaný graf G, a strom s nejkratší cestou zakořeněné na vrcholu proti je kostra T z G, tak, že cesta vzdálenost od kořene proti na jakýkoli jiný vrchol u v T je nejkratší cesta vzdálenost od proti na u v G.

V připojených grafech, kde jsou nejkratší cesty dobře definované (tj. Kde neexistují žádné cykly záporné délky), můžeme sestrojit strom nejkratší cesty pomocí následujícího algoritmu:

  1. Vypočítat vzdálenost (u), nejkratší vzdálenost od kořene proti na vrchol u v G použitím Dijkstrův algoritmus nebo Algoritmus Bellman-Ford.
  2. Pro všechny vrcholy jiných uživatelů než root u, můžeme přiřadit u nadřazený vrchol stru takhle stru je připojen k u, a ten dist (stru) + edge_dist (stru,u) = dist (u). V případě více možností pro stru existují, vyberte si stru pro které existuje nejkratší cesta z proti na stru s co nejmenším počtem hran; toto pravidlo rozbíjení je nutné k zabránění vzniku smyček, pokud existují cykly nulové délky.
  3. Vytvořte strom nejkratší cesty pomocí hran mezi každým uzlem a jeho nadřazeným prvkem.

Výše uvedený algoritmus zaručuje existenci stromů s nejkratší cestou. Jako minimální kostry, stromy s nejkratší cestou obecně nejsou jedinečné.

V grafech, u nichž jsou všechny váhy hran rovny jedné, se shodují nejkratší cesty vyhledávání na šířku stromy.

V grafech, které mají záporné cykly, je sada nejkratších jednoduchých cest z proti na všechny ostatní vrcholy nemusí nutně tvořit strom.

Viz také

Reference

Cahn, Robert S. (1998). Wide Area Network Design: Concepts and Tools for Optimization. Síťování. Morgan Kaufmann. ISBN  978-1558604582.