AOJ - ALDS1_12_A (プリム法) を解いてみた
AOJ - ALDS1_12は、重み付きのグラフアルゴリズムです。
最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge
問題設定
最小全域木というのは、
- 重みがある経路前提
- 閉路がない
グラフにおいて、すべてのノードを一度回るのに最も少ないコストを見つけるための方法です。詳しいところはWikipediaをよめばよろし → 全域木 - Wikipedia
すべてのノードを回るとは言っても、一筆書きは求められていません。一度訪問したノードからは再出発できます。
アルゴリズム
疑似コード
Wikipediaの疑似コードは数学寄りで分かりにくかったです。
それに引き換え、再び参照したサイト from ヨークカレッジ ペンシルバニア校/York College of Pennsylvaniaはいい感じです。また疑似コードを拝借します。
PRIM(G,w,r)
for each u ∈ G.V
u.key = ∞
u.pi = NIL
r.key = 0
Q = G.V
while Q ≠ ∅
u = EXTRACT-MIN(Q)
for each v ∈ G.Adj[u]
if v ∈ Q and w(u,v) < v.key
v.pi = u
v.key = w(u,v)
Lecture 20: Minimum Spanning Trees - Prim's Algorithm
ただ、どちらも求めた最小距離をどうやって合計するかが書かれていない。
コードの工夫など
- INFの表現
到達できないノード、もしくは未発見のノードへの距離は無限とあらわすのが一般的なようで、とりあえず大きい数に置いておいた
- ノードが含む要素
- :u → ノードの番号（１〜）
- :c → 訪問状況を３値（＝３色）で
- :d → ノード間の距離の記録
- :p → 一つ前に探索したノードの記録
INF = 999999999 Node = Struct.new(:u, :d, :c, :p)
*1:経路のノードが膨大になると無理になってくるが
