Rubyでダイクストラ法（ヒープを使わない版）

ダイクストラ法はベルマン-フォード法と同じくグラフの最短路問題を解くアルゴリズム。
ベルマン-フォード法がすべての辺に対して計算を繰り返すのに対して、ダイクストラ法ではコストが最小の頂点をたどって行くために効率的で計算量が少なくて済む。

アルゴリズム図鑑を参考にRubyで実装してみた。辺に重みのついた有向グラフに対して。

ダイクストラ法と言うとだいたい最小ヒープ（優先度付きキュー）を使って実装するのだが、ためしにヒープを使わず実装してみた。

概要

• 各頂点のコスト（重み）を無限（Float::INFINITY）で初期化
• 始点となる頂点からそれぞれ隣接する頂点へのコストを計算（頂点のコスト+辺のコスト）し、既存のコストより小さくなった場合は隣接する頂点のコストを更新
• 未探索の頂点の中からコストのもっとも小さい頂点を次の始点として、そこから隣接する頂点へのコストの計算を繰り返す
• 終点までたどりつき、ほかによりコストの小さい頂点がなくなればそこで終了

コード

Graphはベルマン-フォード法で使ったのと同じものを使う。

# ダイクストラ法で最短路を求める
class ShortestRouteFinder
  def initialize(graph)
    @graph = graph
  end

  def search(from, to)
    p "shortest @vertex_weights from #{from} to #{to}:"

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

    # 未探索の頂点 探索済みになったものから次の始点の対象外として削除していく
    @unexpored_vertexes = @graph.vertexes.keys

    # from自身のコストは0
    @vertex_weights[from] = 0

    # 再帰で現在の頂点に隣接する頂点のコストを更新していく
    current_vertex = from
    update_vertex_weight(current_vertex, to)

    p @vertex_weights
    p @routes
  end

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

    # 隣接する頂点のコストを更新 current_vertexの頂点からのびる辺をすべて処理
    @graph.vertexes[current_vertex].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 
        @unexpored_vertexes.push(k) # 更新されたら未探索に戻す 重複して追加されても大丈夫
        @routes[k] = @routes[current_vertex] + [k] # 経路を記録
      end
    end

    # 未探索から削除 = 探索済みの頂点とする ただし終点は終了判定のための比較に使いたいため未探索のままとする
    @unexpored_vertexes.delete(current_vertex) if current_vertex != goal_vertex
    return if @unexpored_vertexes.empty? # 未探索がなくなったら抜ける

    # 未探索の頂点の中から最少のコストを持つ頂点を次の始点とする
    next_current_vertex = @vertex_weights.select{|k,v| @unexpored_vertexes.include?(k) }.sort{|v1, v2| v1[1] <=> v2[1]}.first[0]

    # 終点が未探索の頂点の中で最小のコストなら抜ける
    return if next_current_vertex == goal_vertex

    update_vertex_weight(next_current_vertex, goal_vertex)
  end
end

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

graph.connect("A", "B", 2)
graph.connect("A", "C", 5)
graph.connect("B", "D", 1)
graph.connect("B", "E", 3)
graph.connect("C", "B", 6)
graph.connect("C", "F", 8)
graph.connect("D", "E", 4)
graph.connect("E", "G", 9)
graph.connect("F", "G", 7)

route_finder = ShortestRouteFinder.new(graph)
route_finder.search("A", "G")
# {"A"=>0, "B"=>2, "C"=>5, "D"=>3, "E"=>5, "F"=>13, "G"=>14}
# {"A"=>["A"], "B"=>["A", "B"], "C"=>["A", "C"], "D"=>["A", "B", "D"], "E"=>["A", "B", "E"], "F"=>["A", "C", "F"], "G"=>["A", "B", "E", "G"]}

頂点をたどって頂点のコストを更新していくupdate_vertex_weightメソッドを再帰呼び出しして、終点まで最小のコストが求まったら終了。

このとき1回のupdate_vertex_weightの始点となる頂点を求める箇所が以下のようになっている。
読みやすくは書けるが、selectとsortの計算量がかかる。

# 未探索の頂点の中から最少のコストを持つ頂点を次の始点とする
next_current_vertex = @vertex_weights.select{|k,v| @unexpored_vertexes.include?(k) }.sort{|v1, v2| v1[1] <=> v2[1]}.first[0]

これを最少ヒープを使えばO(1)の計算量で始点を決められてうれしいというわけ。

次回は最少ヒープから実装してみる。