最短路徑樹

最短路徑樹（shortest-path tree），是一種使用最短路徑算法生成的數據結構樹。

定義

考慮一個連通無向圖${\displaystyle G}$，一個以頂點${\displaystyle v}$為根節點的最短路徑樹${\displaystyle T}$是圖${\displaystyle G}$滿足下列條件的生成樹——樹${\displaystyle T}$中從根節點${\displaystyle v}$到其它頂點${\displaystyle u}$的路徑距離，在圖${\displaystyle G}$中是從${\displaystyle v}$到${\displaystyle u}$的最短路徑距離。

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

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

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

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

外部文獻

• Cahn, Robert S. Wide Area Network Design. 1998.

參見

• 最短路徑問題