ダイクストラ法によるグラフの最短経路の計算を Ruby で書く

「なっとく！アルゴリズム」という本を読んでいる。アルゴリズムの説明が平易かつ丁寧で、イラストもかわいいのでお気に入りだ。

なっとく！アルゴリズム

この書籍の第 7 章で ダイクストラ法 というグラフの最短経路を求めるためのアルゴリズムが紹介されている。書中には説明のために Python のコードが載っているが、今回は復習を兼ねて Ruby で書き直し、かつオブジェクト指向で実装してみることにした。

以下の重み付き有向グラフの最短経路を求める。

require('forwardable')

class Node
  attr_reader :name

  def initialize(name)
    self.name = name
  end

  def ==(other)
    name == other.name
  end

  private

  attr_writer :name
end

class Edge
  attr_reader :from, :to, :weight

  def initialize(from, to, weight = nil)
    self.from = from
    self.to = to
    self.weight = weight
  end

  private

  attr_writer :from, :to, :weight
end

class Graph
  attr_reader :edges

  def initialize(edges)
    self.edges = edges
  end

  def nodes
    @nodes ||= edges.flat_map { |edge| [edge.from, edge.to] }.uniq
  end

  def neighbor_edges_of(node)
    edges.select { |edge| edge.from == node }
  end

  def start_node
    @start_node ||= (nodes - edges.map(&:to)).first
  end

  def finish_node
    @finish_node ||= (nodes - edges.map(&:from)).first
  end

  private

  attr_writer :edges
end

class DijkstrasAlgorithm
  class Node < Node
    attr_accessor :cost, :parent

    def initialize(name:, cost: nil, parent: nil)
      super(name)
      self.cost = cost
      self.parent = parent
      self.processed = false
    end

    def processed!
      self.processed = true
    end

    def processed?
      processed
    end

    private

    attr_accessor :processed
  end

  extend Forwardable

  private_class_method :new

  def self.call(graph)
    new(graph).send(:call)
  end

  private

  attr_accessor :graph
  def_delegators :graph, :nodes, :edges, :neighbor_edges_of, :start_node, :finish_node

  def initialize(original_graph)
    initialize_graph_by(original_graph)
    initialize_node_properties
  end

  def call
    update_node_costs!
    build_shortest_route
  end

  def initialize_graph_by(original_graph)
    new_nodes = initialize_nodes_by(original_graph.nodes)
    new_edges = initialize_edges_by(original_graph.edges, new_nodes)

    self.graph = Graph.new(new_edges)
  end

  def initialize_nodes_by(original_nodes)
    original_nodes.map { |original_node| Node.new(name: original_node.name) }
  end

  def initialize_edges_by(original_edges, new_nodes)
    original_edges.map do |original_edge|
      Edge.new(
        new_nodes.find { |new_node| new_node == original_edge.from },
        new_nodes.find { |new_node| new_node == original_edge.to },
        original_edge.weight
      )
    end
  end

  def initialize_node_properties
    start_edges = edges.select { |edge| edge.from == start_node }
    nodes.each do |node|
      next node if start_node == node

      start_edge = start_edges.find { |edge| edge.to == node }

      if start_edge
        node.cost = start_edge.weight
        node.parent = start_node
      else
        node.cost = Float::INFINITY
        node.parent = nil
      end
    end
  end

  def update_node_costs!
    loop do
      node = find_lowest_cost_node
      break unless node

      neighbor_edges_of(node).each do |edge|
        new_cost = node.cost + edge.weight

        if edge.to.cost > new_cost
          edge.to.cost = new_cost
          edge.to.parent = node
        end
      end

      node.processed!
    end

    true
  end

  def build_shortest_route
    ordered_nodes = [finish_node]

    loop do
      node = nodes.find { |node| node == ordered_nodes.first.parent }
      ordered_nodes.unshift(node)
      break unless node.parent
    end

    ordered_nodes.map { |node| "(#{node.name})" }.join(' -> ')
  end

  def find_lowest_cost_node
    nodes
      .reject { |node| node.cost.nil? || node.processed? }
      .min_by(&:cost)
  end
end

start = Node.new('start')
a = Node.new('a')
b = Node.new('b')
finish = Node.new('finish')

graph = Graph.new([
  Edge.new(start, a, 6),
  Edge.new(start, b, 2),
  Edge.new(a, finish, 1),
  Edge.new(b, a, 3),
  Edge.new(b, finish, 5)
])

DijkstrasAlgorithm.call(graph)
#=> (start) -> (b) -> (a) -> (finish)

# 念のため別のグラフにもアルゴリズムを適用してみる。

start = Node.new('start')
a = Node.new('a')
b = Node.new('b')
c = Node.new('c')
d = Node.new('d')
finish = Node.new('finish')

graph = Graph.new([
  Edge.new(start, a, 5),
  Edge.new(start, b, 0),
  Edge.new(a, c, 15),
  Edge.new(a, d, 20),
  Edge.new(b, c, 30),
  Edge.new(b, d, 35),
  Edge.new(c, finish, 20),
  Edge.new(d, finish, 10)
])

DijkstrasAlgorithm.call(graph)
#=> (start) -> (a) -> (d) -> (finish)

Hash オブジェクトを使って単純に Ruby に翻訳するだけならすぐに終わったけど、クラスを定義してオブジェクト指向で書き直すと非常に時間がかかった。

Graph の構成要素である Node に経路探索コストをそのまま保存している点が気になる。グラフというデータ構造と経路探索コストの計算というアルゴリズムをどうにかして切り離せないだろうか。でも疲れたのでここまで。

↓

アルゴリズムの計算に特化した専用の Node クラスを用意することで、アルゴリズム実行時の副作用を限定できた。ただ代償として、Graph オブジェクトの複製というコストが掛かっている。