ダイクストラ法

2008-09-01
#ruby #algorithm

「最短経路の本」を読んでるところ。アルゴリズムの擬似コードに集合の記号とか使われるとパッと見てわからないね。 ７章の「ローカルに決断して、グローバルに最適化」に続く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 だと配列の「-」でできる

関連記事

新着記事