ダイクストラ法(Ruby)


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

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

def dijkstra(g, s)
  h = g.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] + g[u][v]) < shortest[v]
        shortest[v] = a
        pred[v] = u
      end
    end
  end
  
  [shortest, pred]
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 dijkstra(g, :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 から任意の地点への最短経路が求まっています。


アルゴリズムの基本

アルゴリズムの基本