Rubyでベルマン-フォード法

グラフの最短路問題を解くアルゴリズム。
アルゴリズム図鑑とWikipediaを参考にRubyで実装してみた。辺に重みのついた有向グラフに対して。

概要

• 各頂点のコスト（重み）を無限（Float::INFINITY）で初期化
• 各頂点から順番にそれぞれ隣接する頂点へのコストを計算（頂点のコスト+辺のコスト）し、既存のコストより小さくなった場合は隣接する頂点のコストを更新
• コストの更新がなくなるまでコスト計算をループして繰り返す
• 負の閉路がある場合はコストの更新が永遠に続くのでエラーとする（通常頂点数より多くループが続くことはないので、それを条件に負の閉路の有無を判定する）

コード

# 頂点
class Vertex
  attr_reader :key, :adjacents

  def initialize(key)
    @key = key
    @adjacents = {}
  end

  def connect(vertex, weight)
    @adjacents[vertex.key] = weight
  end
end

# シンプルな有方向グラフ
class Graph
  attr_reader :vertexes

  def initialize
    @vertexes = {}
  end

  def add_vertex(key)
    @vertexes[key] = Vertex.new(key)
  end

  def get_vertex(key)
    @vertexes[key]
  end

  def connect(from, to, weight = 0)
    if !@vertexes.has_key?(from)
      raise "Error: from vertex '#{from}' is not exist"
    end

    raise "Error: to vertex '#{to}' is not exist" if !@vertexes.has_key?(to)

    @vertexes[from].connect(@vertexes[to], weight)
  end
end

class ShortestRouteFinder
  def initialize(graph)
    @graph = graph
  end

  # ベルマン-フォード法
  # fromから各頂点までの最短距離（コスト）を求める
  def search(from)
    p "searching shortest routes from #{from}:"

    # 全頂点に対してコスト無限で初期化
    @vertex_weights = {}
    @routes = {}
    @graph.vertexes.keys.each do |k|
      @vertex_weights[k] = Float::INFINITY
      @routes[k] = [] # fromから各頂点までの最短の経路で通過する頂点を記録
    end

    # from自身のコストは0
    @vertex_weights[from] = 0
    @routes[from].push(from)

    # 全頂点までのコストを計算
    loop_count = 0
    while true
      before_vertex_weights = @vertex_weights.clone

      # 1巡ですべての頂点を1回ずつ処理
      @vertex_weights.keys.each do |key|
        update_vertex_weight(key)
      end

      # コストの変化がなくなったら終了
      break if before_vertex_weights == @vertex_weights

      # 頂点数よりループ回数が多くなった場合は負の閉路ありとみなす
      loop_count += 1
      if loop_count > @graph.vertexes.count
        p @vertex_weights
        raise "Error: 負の閉路があるのでいずれかの頂点のコストが永遠に小さくなり続けるよ"
      end
    end

    p @vertex_weights
    p @routes
  end

  # 頂点に隣接する頂点までのコストを求める
  def update_vertex_weight(vertex_key)
    vertex_weight = @vertex_weights[vertex_key] # 頂点の現在のコスト

    # 隣接する頂点のコストを更新 vertex_keyの頂点からのびる辺をすべて処理
    @graph.vertexes[vertex_key].adjacents.each do |k, adjacent_weight|
      # 新しく求めたコストが小さい場合のみ更新
      new_neighbor_weight = vertex_weight + adjacent_weight
      if @vertex_weights[k] > new_neighbor_weight
        @vertex_weights[k] = new_neighbor_weight 
        @routes[k] = @routes[vertex_key] + [k] # 経路を記録
        # p "vertex: #{k}, from_vertex: #{vertex_key}, weight: #{@vertex_weights[k]}, route: #{@routes[k]}"
      end
    end
  end
end


graph = Graph.new
%w[A B C D E F G].each { |key| graph.add_vertex(key) }

v1 = graph.get_vertex("A")

graph.connect("A", "B", 9)
graph.connect("A", "C", 2)
graph.connect("B", "C", 3)
graph.connect("B", "D", 3)
graph.connect("B", "E", 5)
graph.connect("C", "B", 3)
graph.connect("C", "D", 2)
graph.connect("D", "B", 3)
graph.connect("D", "E", 4)
graph.connect("D", "F", 6)
graph.connect("E", "F", -2)
# A -> C -> D -> B = 5
# A -> C = 2
# A -> C -> D = 4
# A -> C -> D -> E = 8
# A -> C -> D -> E -> F = 6

route_finder = ShortestRouteFinder.new(graph)

route_finder.search("A")
# {"A"=>0, "B"=>5, "C"=>2, "D"=>4, "E"=>8, "F"=>6, "G"=>Infinity}
# {"A"=>["A"], "B"=>["A", "C", "B"], "C"=>["A", "C"], "D"=>["A", "C", "D"], "E"=>["A", "C", "D", "E"], "F"=>["A", "C", "D", "E", "F"], "G"=>[]}

route_finder.search("B")
# {"A"=>Infinity, "B"=>0, "C"=>3, "D"=>3, "E"=>5, "F"=>3, "G"=>Infinity}
# {"A"=>[], "B"=>["B"], "C"=>["B", "C"], "D"=>["B", "D"], "E"=>["B", "E"], "F"=>["B", "E", "F"], "G"=>[]}

グラフの実装が違うとまた違った実装になるだろう。

負の閉路はどこか適当な辺の重みを-10とかにしてみると発生する。
頂点のコストと辺のコストの和がずっとマイナスになってしまうので、新しいコストが既存のコストよりも常に小さくなり続ける。

余談

最初は始点からすべての頂点をたどるのに、変に難しく考えて再帰で頂点から隣接する頂点へのコスト計算をしていたのだが、ベルマン-フォード法の説明をよく読むと、単純に1回のループですべての辺を処理し、ループしていくうちに頂点のコストの更新がなくなったら終了というものだったので、書き直したりしていた。

その実装でも最短路は求められていたけど、1回のループで同じ辺がコスト計算の対象になる回数が多くなるのでやや非効率だった。

2022-11-21コード修正

頂点の重みだけ求めて経路を記録していなかったので記録するようにした。

それと最短路を求めるロジックをGraphクラスからShortestRouteFinderに分離した。