読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】ダイクストラ法(最短経路)。綺麗なコードVer

 
3週間前に書いたコードがあまりに汚くて絶望している。。。

hp12さんのコードをお手本に、もう一度ダイクストラ法を再実装しました。
http://melborne.github.io/2010/01/21/Ruby/

hp12さんすごい。

 

学んだこと

Enumerable#find メソッド!こういうメソッドを探してたんだ。
シンボルの使い方



 

コード(注:ほぼ写経状態です)

DATA = {
 :s => [[5, :a], [4, :b], [2, :c]],
 :a => [[5, :s], [2, :b], [6, :g]],
 :b => [[4, :s], [2, :a], [3, :c], [2, :d]],
 :c => [[2, :s], [3, :b], [6, :d]],
 :d => [[2, :b], [6, :c], [4, :g]],
 :g => [[6, :a], [4, :d]],
 :x => [[2, :y]],
 :y => [[2, :x]]
 }

class Edge
  def initialize(cost, node_id)
    @cost, @node_id = cost, node_id
  end
  attr_reader :cost, :node_id
end
class Node
  def initialize(id, edges, cost=nil, done=false, from=nil)
    @id, @edges, @cost, @done, @from = id, edges, cost, done, from
  end
  attr_accessor :id, :edges, :cost, :done, :from
end
class Graph
  def initialize(data)
    @nodes = data.map do |node_id, edges|
      edges.map!{|edge| Edge.new(*edge)}
      Node.new(node_id, edges)
    end
  end
  def print_route(route)
    return puts "can not reach" if route[0].cost.nil?
    puts route.reverse.map{|node| "#{node.id}(#{node.cost})"}.join("->")
  end
  def minimum_route(start_id, goal_id)
    search_by_dikstra(start_id, goal_id)
    passage = @nodes.find { |node| node.id == goal_id }
    route = [passage]
    while passage = @nodes.find { |node| node.id == passage.from }
      route << passage
    end
    route
  end
  def search_by_dikstra(start_id, goal_id)
    #@nodes変数の初期化.初期化をしないとminimum_routeを複数回行ったときの挙動が誤る
    @nodes.each do |node|
      node.cost = node.id == start_id ? 0 : nil
      node.done = false
      node.from = nil
    end
    loop do
      next_node = nil
      @nodes.each do |node|
        next if node.done || node.cost.nil?
        next_node = node if next_node.nil? || node.cost < next_node.cost
      end
      break if next_node.nil?
      #@nodesを更新
      next_node.done = true
      next_node.edges.each do |edge|
        reachble_node = @nodes.find { |node| node.id == edge.node_id }
        reachble_cost = next_node.cost + edge.cost
        if reachble_node.cost.nil? || reachble_cost < reachble_node.cost
          reachble_node.cost = reachble_cost
          reachble_node.from = next_node.id
        end
      end
    end
  end
end
graph = Graph.new(DATA)
graph.print_route(graph.minimum_route(:s, :g))
graph.print_route(graph.minimum_route(:a, :x))
graph.print_route(graph.minimum_route(:a, :a))