昨日までに書いていたグラフはコストとかそういうの考えていなかったんだけど、ダイクストラをやろうということでコストも考えることにしました。ダイクストラでedgeとそこまでの距離のhashを作りながら、そこまでのを記憶しておくhashも用意。最短路を探す時にはそれを逆向きに再帰で探していきます。
# -*- coding: utf-8 -*- require 'pp' class Graph def initialize(edges=[]) @edges = edges @nodes = Hash.new{|h,k| h[k] = []} @weights = Hash.new{|h,k| h[k] = {}} end def add_edge(edge) @edges.push edge unless @edges.index(edge) end def add_node(u, v) add_edge(u) add_edge(v) unless @nodes[u].index(v) @nodes[u].push v end end def []=(u, v, weight) add_edge(u) add_edge(v) add_node(u, v) @weights[u][v] = weight end def [](u, v) @weights[u][v] end def dijkstra(s) set = [] d = {} set.push s d[s] = 0 path = {} while set.sort != @edges.sort min = 1.0/0 argmin = nil set.each{|u| (@nodes.values.flatten.uniq - set).each{|v| if @nodes[u].include?(v) if min > d[u] + self[u, v] min = d[u] + self[u, v] argmin = {:u => u, :v => v} end end } } if min != 1.0/0 # When there are some routes. path[argmin[:u]] = argmin[:v] set.push argmin[:v] d[argmin[:v]] = min else # When there is no route. break end end return {:d => d, :path => path} end def shortest_path(u, v, d = dijkstra(u), result = [v]) d[:path].each_pair {|key, value| if value == v result.push key shortest_path(u, key, d, result) end } {:path => result.reverse, :d => d[:d]} end end def dijkstra_print(d) puts "The path from #{d[:path][0]} to #{d[:path][d[:path].length-1]} is " + "[#{d[:path].join(" -> ")}], and its distance is #{d[:d][d[:path][d[:path].length-1]]}." end g = Graph.new g["0", "1"] = 2 g["0", "3"] = 7 g["0", "2"] = 3 g["1", "4"] = 1 g["1", "6"] = 6 g["1", "3"] = 4 g["2", "3"] = 4 g["2", "5"] = 1 g["3", "5"] = 2 g["3", "6"] = 3 g["4", "6"] = 4 g["5", "3"] = 1 g["5", "6"] = 2 dijkstra_print(g.shortest_path("0","5")) dijkstra_print(g.shortest_path("1","5")) dijkstra_print(g.shortest_path("0","6")) dijkstra_print(g.shortest_path("1","6"))
グラフはここのやつでやってみた。
/tmp% ruby hash_graph.rb The path from 0 to 5 is [0 -> 2 -> 5], and its distance is 4. The path from 1 to 5 is [1 -> 3 -> 5], and its distance is 6. The path from 0 to 6 is [0 -> 2 -> 5 -> 6], and its distance is 6. The path from 4 to 6 is [4 -> 6], and its distance is 5.
有向路がないときの処理とかやってないけど、まあいいかな。
アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書)
- 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
- 出版社/メーカー: 近代科学社
- 発売日: 2013/12/17
- メディア: 大型本
- この商品を含むブログ (6件) を見る