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

Question

i具有无方向的加权图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的子集。

我的问题是，现在我如何通过参数或引理/定理证明这种最短路径树TM的子树也是最短的树？先感谢您。

Answer 1

好吧，我猜这个spt（最短路径树）只是一个从源到彼此的边缘的树（cos，如果不是这样，它可以包含周期）。

然后，如果您选择原始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。

Answer 2

由于问题还不够清楚，我认为您的问题是以下 -

如果ts =（s，v）是图G =（v，e，w）的最短路径树（扎根于s），则证明ts =（s，k）是TS诱导的子树由k（ subset v）由K。

诱导的g的最短路径树（扎根于s）。

您可以矛盾地证明。

证明（非正式）：让u 在k中成为顶点。由于，u也在v中，因此TS给出的路径p = s-> u最短。假设T不是G'的最短路径树。然后，T路径P = S-> U给出的T不是G'中最短的路径。这意味着，存在另一个顶点v（ in k），因此 p不包含v 和v创建像s-> v-> u这样的快捷方式。

由于ts给出的路径p = s-> u是g， p中最短的一个，必须包含v 在s和u之间的某个位置，这会导致矛盾。

<。