Loading AI tools
来自维基百科,自由的百科全书
最短路径树(shortest-path tree),是一种使用最短路径算法生成的数据结构树。
此條目需要补充更多来源。 (2018年1月5日) |
考虑一个连通无向图,一个以顶点为根节点的最短路径树是图满足下列条件的生成树——树中从根节点到其它顶点的路径距离,在图中是从到的最短路径距离。
在一个所有最短路径都明确(例如没有负长度的环)的连通图中,我们可以使用如下算法构造最短路径树:
上面的算法保证了最短路径树的存在。像最小生成树一样,最短路径树通常也不是唯一的。
在所有边的权重都相同的时候,最短路径树和广度优先搜索树一致。在存在负长度的环时,从到其它顶点的最短简单路径不一定构成最短路径树。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.