algorithm - ダイクストラアルゴリズムの問​​題

Question

グラフにダイクストラアルゴリズムを適用して、結果のツリーが2つの指定された頂点の間にエッジを持たなければならないような方法でMSTを見つけるにはどうすればよいですか？（例：MSTにはXとYの間のエッジが含まれている必要があります）

ありがとう

Answer 1

ダイクストラのアルゴリズムは最短経路 (MST ではない) 用ですが、最小スパニング ツリーを見つけるように変更されたダイクストラのアルゴリズムに似たものは、プリムのアルゴリズムと呼ばれます。Prim のアルゴリズムは、グラフ全体にまたがるまで成長するツリーを保持します。ここで導入された追加の制約はそれほど難しいものではありません。ツリーとして XY から始めるだけです。

具体的には、MST にエッジ (X,Y) を含める必要がある場合 (そのようなエッジが複数ある場合は、最小の重みの 1 つを選択します)、X と Y の 2 つのノードとそれらの間のエッジを持つツリーから始めます。各ステップで、u がツリー内にあり、v が外側にある最小のエッジ (u,v) を選択し、ノード v とエッジ (u,v) をツリーに追加して繰り返します。