すべての都市を最も安く繋ぐ道
複数の都市をケーブルで全て繋ぐとしましょう。ケーブルごとにコストが違い、予算は厳しい。全ての都市が途切れず繋がりつつ、ケーブル総コストを最小にするには、どのケーブルを敷けばよいでしょうか？
このように「全ノードをサイクルなく、最小コストで繋ぐ」木を最小全域木(MST, Minimum Spanning Tree) と呼びます。ノードが \(V\) 個なら、ちょうど \(V-1\) 本の辺で全てが繋がります。
例: A・B・C・D・E・F の6都市を繋ぐMSTの総コストが 19 なら、その19を作る5本の辺を選び出すのが目標です。
MSTを求める代表的なアルゴリズムは2つ。最も安い辺から順に見るクラスカルと、今日見るプリムです。
プリムはどう考える？ (核心アイデア)
クラスカルが「全ての辺をソートして安い順に」見るのに対し、プリムは違います。
1つのノードから出発し、これまで作った木に"最も安く付く辺"を1本ずつ加えて木を育てます。
1. 開始ノードを1つ木に入れる
2. 木に付けられる辺の中で最も安いものを探す
3. その辺で新しいノードを1つ木に編入する
4. 全ノードが入るまで2〜3を繰り返す
雪だるまを転がすように、木という1つの塊が毎回最も安い方向へ1つずつ大きくなります。
なぜわざわざ優先度キューで「辺」を選ぶ？
ここで自然な疑問が浮かびます。「木に付けられる最も安い辺」を毎回どうやって素早く見つける？
木が大きくなるほど、木の境界をまたぐ候補辺は増えたり減ったりします。毎回全部見ると遅い。そこで (辺コスト, その辺が届くノード) を優先度キュー(最小ヒープ) に入れ、取り出す時に常に最も安いものが先に出るようにします。新しいノードを編入するたびにその隣接辺をキューに追加すれば、キューは常に「今木に付けられる候補」をソート済みで保持します。
各ノードごとに key[v] =「vを現在の木に繋ぐ最も安い辺コスト」を覚えておき、より安い辺が現れたら下げます。この「安くなれば更新」がまさに緩和(relaxation)です。
ダイクストラと同じでは？
コードの形は本当に似ています。どちらも優先度キューから (値, ノード) を取り出し、隣接を見て値を更新します。でも 取り出して比較する「値」が違います。
| ダイクストラ | プリム | |
|---|---|---|
| キューに入れる値 | 始点からの累積距離 | 木に1つ付ける1本の辺のコスト |
| 更新式 | dist[u] + w (経路の合計) | w (辺1本) |
| 求めるもの | ある点からの最短経路 | 全体を繋ぐ最小の木 |
ダイクストラは「始点からどれだけ来たか」の合計を測り、プリムは「このノードを木に付ける辺1本」がいくらかだけを見ます。この紙一重の違いが、結果を最短経路 vs 最小全域木へと完全に分けます。
目で見れば確実にわかります
言葉では「距離の合計か辺1本か」が紛らわしいですが、木が1ノードずつ大きくなり、優先度キューが最も安い辺を吐き出す場面を見れば一気に腑に落ちます。
AlgoNoteでは6ノードのグラフでプリムが開始ノードから木を育てていく過程を、key値の更新や優先度キューの変化まで含めて段階的に追えます。どの辺が選ばれ、どの辺が(既に木の中なので)捨てられるか、最終MSTコストがどう19になるかを直接確認してください。