2

無向加重グラフ G=(V,E) があります。ここで、V はノードを表し、E はエッジを表します。ダイクストラ アルゴリズムを使用して、ソース ノード s をルートとし、グラフ G のすべてのノード V にまたがる最短パス ツリー Ts=(s,V) を取得しました。次に、サブツリー Tm=(s,K) を選択しました (ここで Kは、s をすべての V ノードの中で K ノードのみに接続する最短パス ツリー Ts=(s, V) の V) のサブセットです。つまり、サブツリー Tm は、最短パス ツリー Ts のサブセットです。

私の質問は、最短パス ツリー Ts のこのサブツリー Tm も最短ツリーであることを、引数またはレンマ/定理によってどのように証明できるかということです。前もって感謝します。

4

2 に答える 2

0

さて、この SPT (Shortest Path Tree) は、ソースから他の各ノードへのエッジを持つツリーにすぎないと思います (この方法でないと、サイクルが含まれる可能性があります)。

次に、元の SPT のサブツリーを選択すると、ツリーのプロパティを保持する必要があり、いくつかのケースがあります。

  • 自明なツリー: 1 つのノードのみ、エッジなし

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

  • 自明でないツリー: 2 つ以上のノードで、明らかにエッジがあります。

    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 に答える