は物品である：最小スパニングツリーの違いと最短パスツリー
いずれ以下を証明または反例を与える：
（A）最小の頂点の対の間の経路であります無向グラフのスパニングツリー は必然的に最短（最小ウェイト）パスですか？
（b）グラフの最小スパニングツリーが一意であるとします。 無指向性グラフの最小スパニングツリー内の一対の頂点間のパスは、必然的に最短（最小ウェイト）パスですか？
私の答えが
（A）
いいえ、例えば、グラフ0、1、2、0-1のための2-0が5で、1-2は2であり、4であります、その後、（b）は
0-2の真の最短経路は5ですが、MSTは0-1-2で、MSTで、0-2は6
である私の問題は、（b）はこれに入ってきます。
whether the MST is uniqueが最短経路にどのように影響するか分かりません。
最初に、私の理解は、エッジの重みが明確でない場合、複数のMSTが同時に存在する可能性があることです。
第2に、MSTがユニークであっても、上記（a）の回答は（b）に適用されます。
（a）については同意します。
一部のグラフでは、同じ重みを持つ最小限のスパニングツリーが存在する場合があります。頂点a、b、cを有する円C3を考える。重みa→b = 1、b→c = 2、a→c = 2である。このグラフには、{a-b-c}と{c-a-b}の2つのMSTがあります。
それにもかかわらず、あなたの反例はまだ保持されています。なぜなら、MSTはそこで一意であるからです。
だから、非常に簡単なグラフを見てみましょう：
(A)---2----(B)----2---(C)
\ /
---------3----------
このグラフの最小スパニングツリーは、二つのエッジA-BとB-Cで構成されています。他のエッジのセットは、最小スパニングツリーを形成しません。
もちろん、AからCまでの最短パスはA-Cです。これはMSTには存在しません。それがMSTではありませんが存在する短いパスがあるため
EDITだから、（b）の答えはノーである部分に答えるために。
MSTが開始ノードに関連していませんか。
次に、MST開始ノードから最短パスを取得しようとしています。したがって、はい、最短パスはAから始まるMSTによって与えられます！
MSTは、「可能な限り少ないリソース」を使用して*すべてのノードに到達し、最短経路は、* Origin *から* Destination *までの最短経路を提供します。あなたはすでにAからBまで100マイル、BからCは50マイル離れていますが、AからCまでは120マイル離れています。 'A-> C'は確実に' A-> B-> C'よりも短くなりますが、戻るのではなく 'B-> C'を歩きたいでしょうか？ – Goodwine
MSTはどのように定義されていますか？ – Deestan
あなたが言ったように、「ユニーク」は単に「可能なMSTが1つしかない」ということを意味するので、（a）の答えが（b）に当てはまるので、質問は些細で奇妙です。 – Deestan
http://www.me.utexas.edu/~jensen%20/ORMM/methods/unit/network/subunits/mst_spt/index.html – Goodwine