ダイクストラ法(Ruby)


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

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

class Hash
  def dijkstra(s)
    h = map {|x| [x[0], x[1].keys]}.to_h
    
    shortest = Hash.new(Float::INFINITY)
    pred = {}
    done = h.keys.map {|k| [k, false]}.to_h
    
    shortest[s] = 0
    
    loop do
      u = nil
      h.each_key do |node|
        next if done[node]
        u = node if !u or shortest[node] < shortest[u]
      end
      break unless u
      done[u] = true
      
      h[u].each do |v|
        if (a = shortest[u] + self[u][v]) < shortest[v]
          shortest[v] = a
          pred[v] = u
        end
      end
    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}]

下の書籍を参考にして実装しましたが、非常に簡潔に書けていると思います。この例だと s から x までの最短経路は x→t→y→s と戻ればよいので、つまりは s→y→t→x ということですね。見てわかるとおり、s から任意の地点への最短経路が求まっています。


アルゴリズムの基本

アルゴリズムの基本