最短路徑樹

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

定義

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

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

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

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

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

外部文獻

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

參見

• 最短路徑問題