ダイクストラ法(Ruby)


前エントリでは閉路なし有向グラフ(DAG)の場合に最短経路を求めてみましたが、ダイクストラは閉路があり、かつ辺の重みが非負の場合に最短経路を求めることができます。入出力は、閉路があって辺の重みが非負である以外、DAG の場合と同じなので、そちらを見て下さい。

コーディングは Ruby で行いました。返り値は配列 [@shortest, @pred] で、@pred を見ると最短経路がわかります。
dijkstra.rb

require './dag_shortest_paths'

class Hash
  def dijkstra(s)
    #%dis = Rational or Integer or Float, %node = Object
    #Hash{self[%node]: (Hash[%node]: %dis)}, %node{s} ->
    #Hash{h[%node]: Array[%node], @shortest[%node]: %dis, @pred[%node]: %node}
    #%node{q[], u}, %dis{vlu}

    h = map {|x| [x[0], x[1].keys]}.to_h
    
    @shortest = Hash.new(Float::INFINITY)
    @pred = {}
    q = h.keys
    
    @shortest[s] = 0
    
    while q.any?
      vlu = q.map {|k| @shortest[k]}.min 
      u = @shortest.key(vlu)
      q.delete(u)
      h[u].each {|v| relax(u, v)}
    end
    
    [@shortest, @pred]
  end
end

if __FILE__ == $0
  g = {s: {t: 6, y: 4}, t: {x: 3, y: 2},
       x: {z: 4}, y: {z: 3, t: 1, x: 9}, z: {s: 7, x: 5}}
  p g.dijkstra(:s)
end
#=>[{:s=>0, :t=>5, :y=>4, :z=>7, :x=>8}, {:t=>:y, :y=>:s, :z=>:y, :x=>:t}]

dag_shortest_paths.rb は前エントリのコードで、メソッド relax を使っています。下の書籍を参考にして実装しましたが、非常に簡潔に書けていると思います。この例だと s から x までの最短経路は x→t→y→s と戻ればよいので、つまりは s→y→t→x ということですね。見てわかるとおり、s から任意の地点への最短経路が求まっています。


アルゴリズムの基本

アルゴリズムの基本