跳至內容

最短路徑樹

維基百科,自由的百科全書

最短路徑樹(shortest-path tree),是一種使用最短路徑算法生成的數據結構

定義

考慮一個連通無向圖,一個以頂點為根節點的最短路徑樹是圖滿足下列條件的生成樹——樹中從根節點到其它頂點的路徑距離,在圖中是從的最短路徑距離。

在一個所有最短路徑都明確(例如沒有負長度的環)的連通圖中,我們可以使用如下算法構造最短路徑樹:

  1. 使用戴克斯特拉算法貝爾曼-福特算法計算圖 G 中從根節點 v 到 頂點 u 的最短距離
  2. 對於所有的非根頂點,我們可以給分配一個父頂點 連接至u且 。當有多個滿足條件時,選擇從v到的最短路徑中邊最少的。當存在零長度環的時候,這條規則可以避免循環。
  3. 用各個頂點和它們的父節點之間的邊構造最短最短路徑樹。

上面的算法保證了最短路徑樹的存在。像最小生成樹一樣,最短路徑樹通常也不是唯一的。

在所有邊的權重都相同的時候,最短路徑樹和廣度優先搜索樹一致。在存在負長度的環時,從到其它頂點的最短簡單路徑不一定構成最短路徑樹。

外部文獻

參見