最短路徑樹

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

定義

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

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

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

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

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