ダイクストラ法による最短路検索

昨日までに書いていたグラフはコストとかそういうの考えていなかったんだけど、ダイクストラをやろうということでコストも考えることにしました。ダイクストラで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教科書)

アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書)

  • 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
  • 出版社/メーカー: 近代科学社
  • 発売日: 2013/12/17
  • メディア: 大型本
  • この商品を含むブログ (6件) を見る