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

```# -*- 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

@edges.push edge unless @edges.index(edge)
end

unless @nodes[u].index(v)
@nodes[u].push v
end
end

def []=(u, v, weight)
@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件) を見る