最短路徑樹

此條目已列出參考文獻，但因為沒有文內引註而使來源仍然不明。 (2018年1月5日) 请加上合适的文內引註来改善这篇条目。

此條目需要补充更多来源。 (2018年1月5日) 请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。 致使用者：请搜索一下条目的标题（来源搜索："最短路徑樹" — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。

最短路径树（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. 

• 最短路径问题