查看“︁最短路徑樹”︁的源代码

{{no footnotes|time=2018-01-05T01:52:38+00:00}}
{{refimprove|time=2018-01-05T01:52:38+00:00}}
'''最短路径树'''（shortest-path tree），是一种使用[[最短路径问题|最短路径算法]]生成的数据结构[[树 (数据结构)|树]]。

== 定义 ==
考虑一个连通无向图<math>G</math>，一个以顶点<math>v</math>为根节点的最短路径树<math>T</math>是图<math>G</math>满足下列条件的生成树——树<math>T</math>中从根节点<math>v</math>到其它顶点<math>u</math>的路径距离，在图<math>G</math>中是从<math>v</math>到<math>u</math>的最短路径距离。

在一个所有最短路径都明确（例如没有负长度的环）的连通图中，我们可以使用如下算法构造最短路径树：
# 使用[[戴克斯特拉算法]]或[[贝尔曼-福特算法]]计算图 G 中从根节点 v 到 顶点 u 的最短距离<math>dist(u)</math>
# 对于所有的非根顶点<math>u</math>，我们可以给<math>u</math>分配一个父顶点 <math>p_u</math>，<math>p_u</math>连接至u且 <math>dist(p_u) + edge\_dist(p_u,u) = dist(u)</math>。当有多个<math>p_u</math>满足条件时，选择从v到<math>p_u</math>的最短路径中边最少的<math>p_u</math>。当存在零长度环的时候，这条规则可以避免循环。
# 用各个顶点和它们的父节点之间的边构造最短最短路径树。

上面的算法保证了最短路径树的存在。像最小生成树一样，最短路径树通常也不是唯一的。

在所有边的权重都相同的时候，最短路径树和广度优先搜索树一致。在存在负长度的环时，从<math>v</math>到其它顶点的最短简单路径不一定构成最短路径树。

== 外部文献 ==
* {{Cite book|title=Wide Area Network Design|year=1998|url=https://archive.org/details/wideareanetworkd0000cahn|last=Cahn|first=Robert S.}}

== 参见 ==
* [[最短路问题|最短路径问题]]

[[Category:圖算法]]