algorithm - Dijkestraアルゴリズムを実行してPrimと同様にし、MSTを生成するにはどうすればよいですか？

Question

（元の初期ノードと宛先ノードではなく）すべてのノードにアクセスするためにダイクストラアルゴリズムを実行していると仮定します。つまり、宛先ノードではなく、すべてのノードにアクセスするかどうかを確認しています。このアルゴリズムはMST（最小スパニングツリー）を生成しますか？（そしてそれはプリムに似ていますか？）

Answer 1

いいえ。正方形のようなグラフを考えてみましょう。3つのエッジのコスト1はで、残りの1つのエッジのコストは2です。このグラフのMSTにはコストがかかり3ますが、高価なエッジを含む頂点でダイクストラアルゴリズムを開始すると、接続されたノードへの最短パスであるため、そのエッジが使用されます。

クールなASCII視覚化：

    1
 A------B
 |      |
1|      |1
 |      |
 C------D
    2

でダイクストラを開始する場合C、はからへCDの最短パスですが、MSTに含めることはできません。CD

Answer 2

このグラフの例で示されているように、MSTは生成されません。

              ... A
 .... 10 -''''    \
S                  2
 '''' 11 -....      \
              ''''' B

ノードSでダイクストラのアルゴリズムを開始すると、結果のツリーは次のようになります。

              ... A
 .... 10 -''''    
S                 
 '''' 11 -....    
              ''''' B

エッジの全長が21であるのに対し、（この場合は一意の）MSTは次のようになります。

              ... A
 .... 10 -''''    \
S                  2
                    \
                    B

合計12になります。