閉路なし有向グラフ(DAG)の最短経路(Ruby)


上の閉路なし有向グラフ(DAG)のように、辺に「重み」が付いている場合において、最短経路を求めてみます。手続きは

入力:

  • G: n 個の頂点の集合 V と m 本の有向辺の集合 E を含む閉路なし有向グラフ。
  • s: V の始点。

出力:

  • V に含まれる始点以外の頂点 v について、@shortest[v] は s から v への最短経路重み sp(s, v) であり、@pred[v] は何らかの最短経路上で v の直前にある頂点である。始点では、@shortest[s] = 0, @pred[s] = nil であり、s から v へのパスがない場合、@shortest[v] = ∞, @pred[v] = nil である。

 
Ruby でコーディングしてみました。メソッドは [@shortest, @pred] を返します。@pred を見ると最短経路がわかります。
dag_shortest_paths.rb

require './topological_sort'

class Hash
  def dag_shortest_paths(s)
    h = map {|x| [x[0], x[1].keys]}.to_h
    l = h.topological_sort
    
    @shortest = h.keys.map {|k| [k, Float::INFINITY]}.to_h
    @pred = {}
    
    @shortest[s] = 0
    
    l.each do |u|
      h[u].each {|v| relax(u, v)}
    end
    
    [@shortest, @pred]
  end
  
  def relax(u, v)
    if (a = @shortest[u] + self[u][v]) < @shortest[v]
      @shortest[v] = a
      @pred[v] = u
    end
  end
  private :relax
end

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

topological_sort.rb は前エントリのコードです。ハッシュを使うとき、to_h 便利ですね。


念のため、返り値 @pred から最短経路を順に配列に入れて返すメソッドを書いておきます。

class Hash
  def get_order(a)
    order = []
    while a
      order.unshift(a)
      a = self[a]
    end
    order
  end
end

pred = {:t=>:s, :x=>:s, :y=>:x, :z=>:y}
p pred.get_order(:z)    #=>[:s, :x, :y, :z]

 
 

アルゴリズムの基本

アルゴリズムの基本