問題タブ [prims-algorithm]

最小全域木を学んでいます。加重有向グラフのプリムのアルゴリズムを調べます。

アルゴリズムは単純です

• 訪問済みと未訪問の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 のままであるため、更新されません。このツリーには最小コストがありません

私はそれを正しく理解していますか？または私は間違いをしていますか？

ありがとう

ここに表示されているタイプ PriorityVertex は何ですか? getMinSpanningTree メソッドも書いています。

プリムのアルゴリズム

Prim のこの実装で、見つけた最短パスの合計の重みを追跡するのに問題があります。パスは正しいようですが、パスを格納する配列に重みが追加されるため、重みを合計する場所がわかりません (使用されるパスを格納するためだけに書かれているため)。

各頂点が MST に追加されるときに pCrawl->weight を合計しようとしましたが、それはグラフ上のすべての重みの合計のようです。値 key[] と同じです。

私の質問は、すべての最短パスが追加されたときの MST の合計重みを反映するために、パスが MST に追加されるたびに何を合計できるかということです。

私が使用しているコードは次のとおりです。http://pastebin.com/TFLGCE0L

私が作成した隣接リスト: http://pastebin.com/SvgGjEPj

そして、それを作成するために使用された地図:地図

プリムの機能は次のようになります。

使用される構造体は次のようになります。

私はこのデータ構造コースで頭を悩ませているように感じます。そのため、インターネットのコードを使用して、完全な理解なしに課題のこの小さな部分を解決しようとしています:/

ありがとう、

マイケル

水道管の問題を最適化するために Prim のアルゴリズムを使用することを考えています。隣接する頂点が見つかったエッジがある場合に隣接行列を初期化する方法に非常に困惑しています。エッジが存在するたびに重みを付けることを考えました。ただし、w(Vi,Vj) 自体は重み行列のように見えます。では、そもそもなぜ A{Vi,Vj} が必要なのでしょうか。

私がやろうとしているのは、アルゴリズムのアプローチを書き、後でプログラムを書き続けることだけです。以下でよろしいですか？

1. 隣接行列 A{Vi,Vj} を設定します。ここで、Vi には訪問したすべてのノードが含まれ、Vj には訪問した Vi に隣接するすべてのノードが含まれます。以下のマトリックスは、特定の距離を介して隣接する家のペアと接続されているすべての家のペアを格納します。私は混乱しています

   for each Vi:=1 to n do //Vith は i 番目の頂点で 、各 Vj:=1 to n do //Vjth は隣接するハウスのペアであり、その重みは if (Vi とVj) 次に、 A{Vi,Vj} を w(Vi,Vj) で 設定します。それ以外の場合(Vi と Vj の間にエッジが存在しない 場合)、 A[Vi,Vj]:=0を設定します。

2. 最小スパニング ツリーの計算。

3. 出力: 必要な水道管の合計を表示します。