【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))