ベルマン−フォード・アルゴリズム(Ruby)


ベルマン−フォード・アルゴリズムは、ダイクストラ法にさらに辺の重みが負の場合も含めて最短経路を求めることができます。入出力などはダイクストラ法の場合を参照して下さい。

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

require './dag_shortest_paths'

class Hash
  def bellman_ford(s)
    h = map {|x| [x[0], x[1].keys]}.to_h
    
    @shortest = Hash.new(Float::INFINITY)
    @pred = {}
    
    @shortest[s] = 0
    
    (h.size - 1).times do
      h.each do |k, v|
        v.each {|x| relax(k, x)}
      end
    end
    
    [@shortest, @pred]
  end
end

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

dag_shortest_paths.rb はここのコードです。


ベルマン−フォード・アルゴリズム閉路を検出できます。下の find_negative_weight_cycle メソッドで、閉路がない場合は空の配列を、閉路がある場合は閉路の頂点の順番を配列で返します。

class Hash
  def find_negative_weight_cycle(s)
    bellman_ford(s)
    
    each do |u, v1|
      v1.each_key do |v2|
  
        if @shortest[u] + self[u][v2] < @shortest[v2]
          visited = Hash.new(false)
          x = v2
          until visited[x]
            visited[x] = true
            x = @pred[x]
          end
          
          v = @pred[x]
          cycle = [x]
          until v == x
            cycle.unshift(v)
            v = @pred[v]
          end
          return cycle
        end
        
      end
    end
    []
  end
end

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

 
 

アルゴリズムの基本

アルゴリズムの基本