最短路徑樹, 此條目已列出參考文獻, 但因為沒有文內引註而使來源仍然不明, 2018年1月5日, 请加上合适的文內引註来改善这篇条目, 此條目需要补充更多来源, 2018年1月5日, 请协助補充多方面可靠来源以改善这篇条目, 无法查证的内容可能會因為异议提出而移除, 致使用者, 请搜索一下条目的标题, 来源搜索, 网页, 新闻, 书籍, 学术, 图像, 以检查网络上是否存在该主题的更多可靠来源, 判定指引, 最短路径树, shortest, path, tree, 是一种使用最短路径算法生成的数据结构树, 定义, . 此條目已列出參考文獻 但因為沒有文內引註而使來源仍然不明 2018年1月5日 请加上合适的文內引註来改善这篇条目 此條目需要补充更多来源 2018年1月5日 请协助補充多方面可靠来源以改善这篇条目 无法查证的内容可能會因為异议提出而移除 致使用者 请搜索一下条目的标题 来源搜索 最短路徑樹 网页 新闻 书籍 学术 图像 以检查网络上是否存在该主题的更多可靠来源 判定指引 最短路径树 shortest path tree 是一种使用最短路径算法生成的数据结构树 定义 编辑考虑一个连通无向图G displaystyle G 一个以顶点v displaystyle v 为根节点的最短路径树T displaystyle T 是图G displaystyle G 满足下列条件的生成树 树T displaystyle T 中从根节点v displaystyle v 到其它顶点u displaystyle u 的路径距离 在图G displaystyle G 中是从v displaystyle v 到u displaystyle u 的最短路径距离 在一个所有最短路径都明确 例如没有负长度的环 的连通图中 我们可以使用如下算法构造最短路径树 使用戴克斯特拉算法或贝尔曼 福特算法计算图 G 中从根节点 v 到 顶点 u 的最短距离d i s t u displaystyle dist u 对于所有的非根顶点u displaystyle u 我们可以给u displaystyle u 分配一个父顶点 p u displaystyle p u p u displaystyle p u 连接至u且 d i s t p u e d g e d i s t p u u d i s t u displaystyle dist p u edge dist p u u dist u 当有多个p u displaystyle p u 满足条件时 选择从v到p u displaystyle p u 的最短路径中边最少的p u displaystyle p u 当存在零长度环的时候 这条规则可以避免循环 用各个顶点和它们的父节点之间的边构造最短最短路径树 上面的算法保证了最短路径树的存在 像最小生成树一样 最短路径树通常也不是唯一的 在所有边的权重都相同的时候 最短路径树和广度优先搜索树一致 在存在负长度的环时 从v displaystyle v 到其它顶点的最短简单路径不一定构成最短路径树 外部文献 编辑Cahn Robert S Wide Area Network Design 1998 参见 编辑最短路径问题 取自 https zh wikipedia org w index php title 最短路徑樹 amp oldid 75590014, 维基百科，wiki，书籍，书籍，图书馆，
