ダイクストラ法~線形探索~
Rubyでダイクストラ法の実装を行います。
探索済みとなる要素は線形探索しています。
(こちらのコードをrubyコードに変換することで実装させてもらいました。)
$MAX_V = 6 $INF = 100000 def dijkstra(s) cost = [ [$INF, 2, 5, $INF, $INF, $INF, $INF], [2, $INF, 4, 6, 10, $INF, $INF], [5, 4, $INF, 2, $INF, $INF, $INF], [$INF, 6, 2, $INF, $INF, 1, $INF], [$INF, 10, $INF, $INF, $INF, 3, 5], [$INF, $INF, $INF, 1, 3, $INF, 9], [$INF, $INF, $INF, $INF, 5, 9, $INF]] d = [] used = [] d.fill($INF,0..$MAX_V) used.fill(false,0..$MAX_V) d[s] = 0 while(1) v = -1 for u in 0..$MAX_V do if !used[u] && (v == -1 || d[u] < d[v]) then v = u end end if v == -1 then break end used[v] = true for u in 0..$MAX_V do d[u] = d[u] < (d[v] + cost[v][u]) ? d[u] : (d[v] + cost[v][u]) end end return d end print dijkstra(0)
実行結果です。途中のノード番号などを出力はしていません。
[0, 2, 5, 7, 11, 8, 16] Complete(0)
線形探索部分が下記の部分です。
条件文は(ノードが確定しているかのフラグ && 未訪問 || 現在値よりも小さい)
と読めます。
for u in 0..$MAX_V do if !used[u] && (v == -1 || d[u] < d[v]) then v = u end end
経路更新は下記の部分です。
対象すると経路(d[u])に対して、新規経路(d[v] + cost[v][u])の方が短いかどうか
を判定し、その結果を代入しています。
途中のノード番号を保持するならばここに追加コードが必要です。
for u in 0..$MAX_V do d[u] = d[u] < (d[v] + cost[v][u]) ? d[u] : (d[v] + cost[v][u]) end
今回は線形探索で実装しましたが、次はプライオリティキューを用いて実装したいです。