首页 文章

最短路径树的子树也是最短的树？

提问于
浏览 次
2

我有一个无向加权图G =（V，E），其中V代表节点，E代表边 . 通过Dijkstra算法，我得到了一个最短路径树Ts =（s，V），它根源于源节点s并跨越图G中的所有节点V.然后我选择了一个子树Tm =（s，K），（其中K是最短路径树Ts =（s，V）的V）的子集，其将s连接到所有V个节点中的仅K个节点，即，子树Tm是最短路径树Ts的子集 .

我的问题是现在我怎么能通过参数或引理/定理来证明这个最短路径树Ts的子树Tm也是最短的树？先感谢您 .

algorithm tree dijkstra undirected-graph

2 回答

  • 0

    好吧，我猜这个SPT（最短路径树）只是一个从源到另一个节点的边缘的树（如果它不是这样的cos，它可能包含循环） .

    然后，如果您选择原始SPT的某个子树，您将必须保留树的属性，然后我们有一些情况：

    • Trivial Tree：只有一个节点，没有边缘
    no problems in here, it's a SPT (empty)
    • Not-Trivial Tree：两个或更多节点，显然有边缘 .
    this is kind of tricky. 

if you suppose that this sub-tree is rooted on source, then its easy
to see that the sub-tree will be a set of shortest paths between
the source and the other nodes, making it be a SPT ROOTED ON SOURCE.

otherwise, it wont be a SPT, cause if its rooted on some other node
(instead of source), the path from the root to other node (different
from source) may not be minimum.

    我猜您对源自源的子树感兴趣，但很容易看到子树只包含最短路径（因为它是SPT本身的子树），然后它将是一个SPT .

    回复于
  • 0

    由于问题不够明确，我认为你的问题如下 -

    如果Ts =（s，V）是图G =（V，E，W）的最短路径树（以s为根），则证明T's =（s，K），由K引起的Ts的子树（\子集V）是由K引起的G的子图G'=（K，E'，W）的最短路径树（以s为根） .

    你可以通过矛盾来证明 .

    证明（非正式）：让你在K中成为一个顶点 . 因为，u也在V中，Ts给出的路径p = s - > u是最短的 . 假设，T 's is not a shortest path tree of G' . 然后路径p = s - > u由T 's is not the shortest in G'给出 . 这意味着，存在另一个顶点v（在K中为\），使得p不包含v，而v创建了一个类似s - > v - > u的快捷方式 .

    由于Ts给出的路径p = s - > u是G中最短的，所以p必须在s和u之间的某处包含v，这导致矛盾 .

    回复于

相关问题