algorithm - 最短路径树的子树也是最短树吗？

Question

我有一个无向加权图 G=(V,E)，其中 V 代表节点，E 代表边。通过 Dijkstra 算法，我得到了一棵以源节点 s 为根并跨越图 G 中所有节点 V 的最短路径树 Ts=(s,V)。然后我选择了一棵子树 Tm=(s,K)，(其中 K是最短路径树Ts=(s, V)的V)的一个子集，它把s连接到所有V节点中只有K个节点，即子树Tm是最短路径树Ts的一个子集。

我的问题是现在如何通过论证或引理/定理证明最短路径树 Ts 的子树 Tm 也是最短树？。先感谢您。

Answer 1

好吧，我猜这个 SPT(最短路径树)只是一棵从源到每个其他节点都有边的树(因为如果不是这样，它可能包含循环)。

然后，如果你选择原始SPT的一些子树，你将不得不保留树的属性，那么我们有一些情况:

• 普通树:只有一个节点，没有边

  no problems in here, it's a SPT (empty)
  

• 非平凡树:两个或多个节点，显然有边。

  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。