ダイクストラ法

2008-09-01

最短経路の本」を読んでるところ。アルゴリズムの擬似コードに集合の記号とか使われるとパッと見てわからないね。 7章の「ローカルに決断して、グローバルに最適化」に続くp.57の最短経路を求めるダイクストラ法をRubyで実装:

# 無限大の距離
INF = 10**10

#=== s から v への直接の距離
#
#_s_ :: 移動元頂点
#_v_ :: 移動先頂点
#_E_ :: 距離グラフ
#
# s から直接 v へ行けない場合、無限大を返す
#
def arclength(s, v, _E)
if _E.has_key?(s) && _E[s].has_key?(v)
_E[s][v]
else
INF
end
end


#=== ダイクストラのアルゴリズムで _s_ から _z_ への最小距離と経路を返す
#
#_V_ :: 頂点配列
#_E_ :: 距離グラフ
#_s_ :: 出発位置
#_z_ :: 目的位置
#
def dijkstra(_V, _E, s, z)
distance = {}
predecessor = {}

_S = [s]
distance[s] = 0
(_V - _S).each do |v|
distance[v] = arclength(s, v, _E)
predecessor[v] = s
end

until _S.include?(z)
v_star = (_V - _S).min_by {|v| distance[v]}
_S.push(v_star)
(_V - _S).each do |v|
if distance[v_star] + arclength(v_star, v, _E) < distance[v]
distance[v] = distance[v_star] + arclength(v_star, v, _E)
predecessor[v] = v_star
end
end
end

return distance[z], predecessor
end

テスト:

_V = [
:s,
:z,

:a,
:b,
:c,
:d,
:e,
:f,
]

_E = {
:s => {
:a => 3,
:b => 5,
},
:a => {
:b => 1,
:c => 10,
:d => 11,
},
:b => {
:a => 3,
:c => 2,
:d => 3,
},
:c => {
:d => 2,
:e => 7,
:f => 12,
},
:d => {
:a => 15,
:b => 7,
:f => 2,
},
:e => {
:d => 11,
:z => 2,
},
:f => {
:e => 3,
:z => 2,
},
}

p dijkstra(_V, _E, :s, :z)

結果:

$ ruby dijkstra.rb
[11, {:e=>:f, :f=>:d, :a=>:s, :z=>:f, :b=>:a, :c=>:b, :d=>:b}]
  • 本の中のバックスラッシュ「\」は差集合、Ruby だと配列の「-」でできる