Loading AI tools
来自维基百科,自由的百科全书
最短路徑樹(shortest-path tree),是一種使用最短路徑算法生成的數據結構樹。
此條目需要補充更多來源。 (2018年1月5日) |
考慮一個連通無向圖,一個以頂點為根節點的最短路徑樹是圖滿足下列條件的生成樹——樹中從根節點到其它頂點的路徑距離,在圖中是從到的最短路徑距離。
在一個所有最短路徑都明確(例如沒有負長度的環)的連通圖中,我們可以使用如下算法構造最短路徑樹:
上面的算法保證了最短路徑樹的存在。像最小生成樹一樣,最短路徑樹通常也不是唯一的。
在所有邊的權重都相同的時候,最短路徑樹和廣度優先搜索樹一致。在存在負長度的環時,從到其它頂點的最短簡單路徑不一定構成最短路徑樹。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.