Dijkstraのアルゴリズムの FigureSP03-01をRubyで書いてみました。
Infinity = 9999 class Node attr_reader :status, :node_distance, :temporary_distance, :decision_distance, :id, :parent, :nodes def initialize(id, distance, parent) @id = id @nodes = [] @node_distance = distance @temporary_distance = Infinity @decision_distance = Infinity @parent = parent end def show puts "id:#{@id} n:#{@node_distance} " + "tmp:#{@temporary_distance} " + "decision:#{@decision_distance} nodes:[#{childs_name_distance}]" end def childs_name_distance string = "" @nodes.each{|node| string += "(#{node.node_distance} #{node.id})" } string end def set_root decision(0) set_temp(0) end def temporary(parent_distance) if @temporary_distance>(parent_distance + @node_distance) @temporary_distance = parent_distance + @node_distance end end def decision(distance) @decision_distance = distance end def set_temp(distance) @temporary_distance = distance end end class Graph def initialize(root_name) @root = Node.new(root_name, 0, :root) @root.set_root end def add_node(p, id, distance) parent = search_node(p) # 新しく追加しようとする親ノード # 既に同じノードがあれば長い方を切断 if exist?(id) exist = search_node(id) #puts "既存のノード：仮の距離 #{@root.get_node(id).temporary_distance}" #puts "新しく追加するノード：仮の距離 #{node.tmp_regist_distance("D",4)}" # 新しく追加するノードが短かければ # 古いノードを削除して新しノードを追加。 if tmp_regist_distance(parent, id, distance) < exist.temporary_distance del_node(id) parent.nodes.push(temporary_regist(parent, id, distance)) end else parent.nodes.push(temporary_regist(parent, id, distance)) end end def temporary_regist(parent_node, id, distance) node = Node.new(id, distance, parent_node) node.temporary(parent_node.decision_distance) # 仮の距離を設定 node end def tmp_regist_distance(parent_node, id, distance) temporary_regist(parent_node, id, distance).temporary_distance end def shortest_path(id) shortest_path_(search_node(id),[]).reverse.join(":") end def shortest_path_(node, array) unless node.parent == :root array.push("#{node.parent.id} = #{node.node_distance} = #{node.id}") shortest_path_(node.parent, array) end array end def search_node(id); search_node_(@root,id) end def search_node_(node,id) return node if node.id == id node.nodes.each do |n| if n.id == id return n else child = search_node_(n,id) return child if child.is_a?(Node) end end false end def del_node(id); del_node_(@root,id) end def del_node_(node,id) unless node.nodes.select{|n| n.id == id }.size.zero? node.nodes.delete_if{|n| n.id == id} else node.nodes.each{|n| del_node_(n,id)} end end def exist?(id) search_node(id).is_a?(Node) end def show_all; show_all_(@root) end def show_all_(node) node.show node.nodes.each{|n| show_all_(n) } end # 仮の最短距離が一番小さいノードを返す。 def shortest_node; shortest_node_(@root) end def shortest_node_(n) shortest_node_distance = Infinity shortest = nil n.nodes.each do |node| if node.decision_distance == Infinity if shortest_node_distance > node.temporary_distance shortest_node_distance = node.temporary_distance shortest = node end end child_shortest = shortest_node_(node) if shortest.nil? && child_shortest.is_a?(Node) shortest = child_shortest elsif shortest.is_a?(Node) && child_shortest.is_a?(Node) if shortest.temporary_distance > child_shortest.temporary_distance shortest = child_shortest end end end shortest end end g = Graph.new("A") # 始点Aを登録 g.add_node("A", "C", 3) # ノードAにCを登録 g.add_node("A", "B", 5) # ノードAにBを登録 shortest = g.shortest_node # A から最短のノード shortest.decision(shortest.temporary_distance) # shortest.show #=> id:C n:3 tmp:3 decision:3 nodes:[] # C 決定 puts g.shortest_path(shortest.id) #=> A = 3 = C g.add_node(shortest.id, "E", 4) g.add_node(shortest.id, "G", 8) g.add_node(shortest.id, "F", 6) g.add_node(shortest.id, "D", 2) shortest = g.shortest_node shortest.decision(shortest.temporary_distance) # shortest.show #=> id:B n:5 tmp:5 decision:5 nodes:[] # B 決定 puts g.shortest_path(shortest.id) #=> A = 5 = B # B の最短経路 g.add_node(shortest.id, "D", 4) shortest = g.shortest_node shortest.decision(shortest.temporary_distance) # shortest.show #=> id:D n:2 tmp:5 decision:5 nodes:[] # g.show_all puts g.shortest_path(shortest.id) #=> A = 3 = C:C = 2 = D # D の最短経路 g.add_node(shortest.id, "F", 3) shortest = g.shortest_node shortest.decision(shortest.temporary_distance) # shortest.show #=> id:E n:4 tmp:7 decision:7 nodes:[] puts g.shortest_path(shortest.id) #=> A = 3 = C:C = 4 = E # E の最短経路 g.add_node(shortest.id, "G", 6) shortest = g.shortest_node shortest.decision(shortest.temporary_distance) puts g.shortest_path(shortest.id) #=> A = 3 = C:C = 2 = D:D = 3 = F g.add_node(shortest.id, "G", 4) g.add_node(shortest.id, "H", 4) shortest = g.shortest_node shortest.decision(shortest.temporary_distance) puts g.shortest_path(shortest.id) #=> A = 3 = C:C = 8 = G g.add_node(shortest.id, "I", 5) g.add_node(shortest.id, "H", 2) shortest = g.shortest_node shortest.decision(shortest.temporary_distance) puts g.shortest_path(shortest.id) #=> A = 3 = C:C = 2 = D:D = 3 = F:F = 4 = H g.add_node(shortest.id, "I", 7) g.add_node(shortest.id, "J", 6) shortest = g.shortest_node shortest.decision(shortest.temporary_distance) puts g.shortest_path(shortest.id) #=> A = 3 = C:C = 8 = G:G = 5 = I g.add_node(shortest.id, "K", 4) g.add_node(shortest.id, "J", 1) shortest = g.shortest_node shortest.decision(shortest.temporary_distance) puts g.shortest_path(shortest.id) #=> A = 3 = C:C = 8 = G:G = 5 = I:I = 1 = J g.add_node(shortest.id, "K", 5) shortest = g.shortest_node shortest.decision(shortest.temporary_distance) # shortest.show #=> id:K n:4 tmp:20 decision:20 nodes:[] puts g.shortest_path(shortest.id) #=> A = 3 = C:C = 8 = G:G = 5 = I:I = 4 = K # K の最短経路 g.show_all #=> id:A n:0 tmp:0 decision:0 nodes:[(3 C)(5 B)] # id:C n:3 tmp:3 decision:3 nodes:[(4 E)(8 G)(2 D)] # id:E n:4 tmp:7 decision:7 nodes:[] # id:G n:8 tmp:11 decision:11 nodes:[(5 I)] # id:I n:5 tmp:16 decision:16 nodes:[(4 K)(1 J)] # id:K n:4 tmp:20 decision:20 nodes:[] # id:J n:1 tmp:17 decision:17 nodes:[] # id:D n:2 tmp:5 decision:5 nodes:[(3 F)] # id:F n:3 tmp:8 decision:8 nodes:[(4 H)] # id:H n:4 tmp:12 decision:12 nodes:[] # id:B n:5 tmp:5 decision:5 nodes:[]
