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 也是最短树？先感谢您。

4

2 回答 2

0

由于问题不够清楚，我假设您的问题如下 -

如果 Ts=(s,V) 是图 G = (V,E,W) 的最短路径树（以 s 为根），则证明 T's = (s, K) 是由 K 诱导的 Ts 的子树（ \subset V)，是由 K 诱导的 G 的子图 G' = (K,E',W) 的最短路径树（以 s 为根）。

你可以用反证法来证明。

证明（非正式）：设 u \in K 是一个顶点。由于 u 也在 V 中，所以由 Ts 给出的路径 p = s -> u 是最短的。假设 T's 不是 G' 的最短路径树。那么 T's 给出的路径 p = s -> u 不是 G' 中最短的。这意味着，存在另一个顶点 v (\in K) 使得p 不包含 v并且 v 创建了一个快捷方式，如 s -> v -> u。

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

于 2018-06-17T06:30:43.537 回答
0

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

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

  • 平凡树：只有一个节点，没有边

    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。

于 2016-12-28T19:51:21.213 回答