ダイクストラ法による最短経路の計算
https://gyazo.com/e5956ad9d1f3ff75979de2f1de92f8f4
プログラミングの基礎 の「ダイクストラのアリゴリズム（112ページ）」を雑にRubyで実装した。書き散らかしの汚いコードだけど、アルゴリズムを理解して満足しちゃったので、修正するモチベーションが湧かないや...
code:dijkstra.rb
# ダイクストラ法による最短経路の計算
#
# $ ruby dijkstra.rb
# A: 0, "A"
# B: 9, "A", "D", "E", "B"
# C: 8, "A", "D", "E", "C"
# D: 4, "A", "D"
# E: 7, "A", "D", "E"
# F: 104, "A", "D", "F"
# G: 304, "A", "D", "F", "G"
# ----------------------------------------
# U: "A", "D", "E", "C", "B", "F", "G"
# V: []
class Node
# ノードが持つ「始点からの距離」の最大値。ある程度の大きさの値ならなんでも良い
MAX = 999999999
attr_accessor :name, :val, :route
def initialize(name, val = MAX, route = [])
# ノード名
@name = name
# 始点からの距離（<- 計算結果がここに格納される）
@val = val
# タイクストラ法により計算される「始点からの経路」（<- 計算結果がここに格納される）
# （経路がA->B->Cの場合、"A", "B", "C" が格納される）
@route = route
end
end
class Edge
attr_reader :from, :to, :length
def initialize(from, to, length)
@from = from # FROMノード名
@to = to # TOノード名
@length = length # FROMノードからTOノードまでの距離
end
end
class Graph
attr_reader :nodes
def initialize
@nodes = {} # グラフに含まれるノード一覧
@edges = [] # グラフに含まれるエッジ一覧（ノードの接続と距離を持つ）
@u = [] # U集合: 距離が確定したノード一覧
@v = [] # V集合: 距離が確定していないノード一覧
end
# グラフへノードを追加
def add_node(node_name)
@nodesnode_name = Node.new(node_name, Node::MAX, [])
@v << node_name # グラフへ追加されたノードをV集合へ追加
end
# グラフへエッジを追加
def add_edge(from, to, length)
@edges << Edge.new(from, to, length)
end
# 始点ノードを規定の方法で初期化
def init_start_node(from)
start_node = @nodesfrom
# 始点のノードの距離は「0」
start_node.val = 0
# 始点のノード　"A" の経路は "A"
start_node.route = from
# 始点ノードの距離は確定してるので、U集合へ始点ノードを追加し、V集合から始点ノードを削除
@u << @v.delete(from)
end
# 始点 from からの最短経路を計算する
def dijkstra(from)
return if @v.empty?
# 「FROMノード」につながるノード一覧を取得
from_node = @nodesfrom
target_node_names = linked_node_names(from) - @u
target_nodes = @nodes.values.filter {|node| target_node_names.include?(node.name) }
# 対象となるノードの最短距離を更新
target_nodes.each do |node|
update_val(node.name, from_node)
end
# V集合の中で最も最短距離のノードを確定させる
min_node = v_nodes.min_by {|node| node.val }
@u << @v.delete(min_node.name) # V集合から削除し、U集合へ追加
# 直前に確定したノードにつながるノードの最短距離を計算する
dijkstra(min_node.name)
end
# FROMノードにつながるノードの名前一覧を取得
def linked_node_names(from)
node_names = []
node_names += @edges.filter {|edge| edge.from == from }.map(&:to)
node_names += @edges.filter {|edge| edge.to == from }.map(&:from)
node_names.sort.uniq
end
# 指定したノードの最短距離を更新する
def update_val(target_node_name, from_node)
from_node_name = from_node.name
target_node = @nodestarget_node_name
from_node = @nodesfrom_node_name
edge = find_edge(from_node_name, target_node_name)
if (edge.length + from_node.val) < target_node.val
target_node.val = edge.length + from_node.val
target_node.route = from_node.route + target_node_name
end
end
# エッジを取得
def find_edge(from, to)
@edges.find {|e| (e.from == from && e.to == to) || (e.from == to && e.to == from) }
end
# V集合に所属するノード一覧を取得
def v_nodes
@v.map {|k| @nodesk }
end
# 計算結果をいい感じに出力する
def to_s
lines = @nodes.map do |key, node|
"#{node.name}: #{node.val}, #{node.route}"
end
lines << "----------------------------------------"
lines << "U: #{@u}"
lines << "V: #{@v}"
lines.join("\n")
end
end
# メイン
g = Graph.new
g.add_node "A"
g.add_node "B"
g.add_node "C"
g.add_node "D"
g.add_node "E"
g.add_node "F"
g.add_node "G"
g.add_edge "A", "B", 10
g.add_edge "B", "C", 2
g.add_edge "A", "D", 4
g.add_edge "D", "E", 3
g.add_edge "B", "E", 2
g.add_edge "E", "C", 1
g.add_edge "D", "F", 100
g.add_edge "F", "G", 200
g.init_start_node("A")
g.dijkstra("A")
puts g.to_s