最小全域木を学んでいます。加重有向グラフのプリムのアルゴリズムを調べます。
アルゴリズムは単純です
- 訪問済みと未訪問の2つの頂点セットがあります
- すべてのエッジの距離を無限に設定
- 訪問されていないセットの任意の頂点から開始し、そのエッジを探索します
- すべてのエッジで、目的の頂点が訪問されておらず、エッジの重みが目的の頂点の距離よりも小さい場合、目的の頂点の距離をエッジの重みで更新します
- 距離が最も小さい未訪問の頂点を選択し、すべての頂点が訪問されるまでそれを繰り返します
上記のアルゴリズムを使用すると、すべてのスパニング ツリーの中で最小のコストを持つスパニング ツリー、つまり最小スパニング ツリーを見つけることができると思います。
しかし、次の例に適用しましたが、失敗したと思います。
次の例を検討してください
頂点は {v1,v2,v3,v4,v5} で、辺の重みは
(x,y) : w =>
(v1,v2) : 8
(v1,v3) : 15
(v1,v4) : 7
(v2, v5) : 4
(v4、v5) : 7
最初に v1 を探索します。v2、v3、v4 へのエッジがあるため、グラフは
頂点 v1 にアクセスし、(頂点、距離) =>
(v2,8)
(v3,15)
(v4,7)
v4 の距離が最小になりますつまり 7 なので、v4 を探索します。v5 へのエッジがあるため、次の変更が発生します
頂点 v4 が訪問され、(頂点、距離) => (v5,7)
すべての v5 の中で、距離が最小、つまり 7 であるため、v5 を探索しますが、エッジがないため、訪問済みとマークするだけです
頂点 v5 にアクセス
さあ、ここから混乱が始まる
最小距離の頂点は現在 v2 であり、重み 4 の v5 へのエッジがあり、現在 v5 の距離は 7 であり、以前はエッジ (v4,v5) : 7 によって割り当てられていたので、最小スパニング ツリーを作成するには、v5 の距離は 4 < 7 として 7 から 4 に更新する必要がありますが、v5 が既に訪問されており、Prim のアルゴリズムが既に訪問されている頂点の距離を更新せず、v5 の距離が 4 ではなく 7 のままであるため、更新されません。このツリーには最小コストがありません
私はそれを正しく理解していますか？または私は間違いをしていますか？
ありがとう