最短路径树（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到其它顶点的最短简单路径不一定构成最短路径树。

外部文献
*

参见

• 最短路径问题