[科普中国]-最短路径树

最短路径树(Shortest Path Tree, SPT)，是一种使用最短路径算法生成的数据结构树。

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

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

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

对于所有的非根顶点 ，我们可以给 分配一个父顶点 ， 连接至u且 。当有多个 满足条件时，选择从v到 的最短路径中边最少的 。当存在零长度环的时候，这条规则可以避免循环。

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

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

相关算法Dijkstra算法设置两个定点的集合T和S，集合S中存放已找到最短路径的定点，集合T中存放当前还未找到的最短路径的定点。初始状态时，集合S中只包含源点v0然后不断从集合T中选取到定点v0路径长度最短的顶点u加入集合S，集合S中每加入一个新的顶点u，都要修改定点v0到集合T中剩余顶点的最短路径长度值，集合T中每个顶点新的最短路径长度值为原来的最短路径长度值与定点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到集合S为止1。

Floyd算法从代表任意两个节点 到 距离的带权邻接矩阵D(0)开始，首先计算D(1)，即计算Vi到Vj经过一次经转的所有可能路径，经过比较后选出最短路，代替D(0)中对应的路径，迭代列出距离矩阵D(1)，D(1)中各元素表示通过一次迭代后网络中任意两点间最短路，也即网络中任意两点之间直接到达或只经过一个中间点时的最短路。在此基础上依次计算D(2)，D(3)，…，D(k)，D(k)中对应的元素表示任意两点间不经过中间点或最多允许经过2k+1个中间点时的最短路。当D(k+1)=D(k)时，表明得到的带权邻接矩阵D(k)就反映了所有顶点对之间的最短距离信息，成为最短距离矩阵。

本词条内容贡献者为:

吴晨涛 - 副研究员 - 上海交通大学