最短路徑樹

最短路径树(shortest-path tree),是一种使用最短路径算法生成的数据结构

定义

考虑一个连通无向图 ,一个以顶点 为根节点的最短路径树 是图 满足下列条件的生成树——树 中从根节点 到其它顶点 的路径距离,在图 中是从  的最短路径距离。

在一个所有最短路径都明确(例如没有负长度的环)的连通图中,我们可以使用如下算法构造最短路径树:

  1. 使用戴克斯特拉算法贝尔曼-福特算法计算图 G 中从根节点 v 到 顶点 u 的最短距离 
  2. 对于所有的非根顶点 ,我们可以给 分配一个父顶点   连接至u且  。当有多个 满足条件时,选择从v到 的最短路径中边最少的 。当存在零长度环的时候,这条规则可以避免循环。
  3. 用各个顶点和它们的父节点之间的边构造最短最短路径树。

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

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

外部文献

参见