建设工程知识

最短路径树定义

考虑一个连通无向图

，一个以顶点

为根节点的最短路径树

是图

满足下列条件的生成树——树

中从根节点

到其它顶点

的路径距离，在图

中是从

到

的最短路径距离。

在一个所有最短路径都明确（例如没有负长度的环）的连通图，我们可以使用如下算法构造最短路径树：

使用Dijkstra算法或Floyd算法计算图 G 从根节点 v 到 顶点 u 的最短距离

。

对于所有的非根顶点

，我们可以给

分配一个父顶点

，

连接至u且

。当有多个

满足条件时，选择从v到

的最短路径中边最少的

。当存在零长度环的时候，这条规则可以避免循环。

用各个顶点和它们的父节点之间的边构造最短最短路径树。

上面的算法保证了最短路径树的存在。像最小生成树一样，最短路径树通常也不只有一个的。在所有边的权重都相同的时候，最短路径树和广度优先搜索树一致。在存在负长度的环时，从

到其它顶点的最短简单路径不一定构成最短路径树。

• 上一篇：[湖北]钟祥：市住建局2015年全力推进五大工程
• 下一篇：国鑫铝业攻克超硬铝薄壁管材技术难关
• 关键词： 最短路径树定义 最短路径树