dijkstra

Rubyで最短経路を探索しよう！ - hp12c
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ 跡地
ダイクストラ法（最短経路問題）

頭で消化したつもりなので清書。
うーん、径路の遡りが醜い、醜すぎるので後で直す。
これを宣言的に書くにはどうするんだろう?
本当は scheme で書けるようになっておきたい。

def dijkstra(node_data)
  nodes = {}
  node_data.each {|k,v|
    nodes[k] = Node.new(k, v)
  }
  nodes["s"].cost = 0
  
  puts "#### initialize"
  puts nodes.values.join("\n")
  
  focus_node = nodes["s"]
  while focus_node
    focus_node.done = true
    focus_node.link.each_with_index {|key,i|
      newcost = focus_node.cost + focus_node.link_cost[i]
      edge_node = nodes[key]
      if newcost < edge_node.cost
        edge_node.cost = newcost
        edge_node.done = false if edge_node.done
      end
    }

    focus_node = nodes.values.select{|node|
      ! node.done and node.key != focus_node.key
    }.sort{|a, b|
      a.cost<=>b.cost
    }.first
  end

  puts "#### calculated"
  puts nodes.values.join("\n")
  nodes
end

def traverse(node)
  node.link.each_with_index{|key,i|
    if $result[key].link.find{|k|k=="s"}
      if (node.cost - node.link_cost[i]) == $result[key].cost
        return [node.key, key, "s"]
      end
    else
      return [node.key].concat(traverse($result[key]))
    end
  }
  
end

node_data = {
  "s" => [["a", 5], ["b", 6], ["c", 2]],
  "a" => [["s", 5], ["b", 2], ["g", 6]],
  "b" => [["s", 6], ["a", 2], ["c", 3], ["d", 2]],
  "c" => [["s", 2], ["b", 3], ["d", 6]],
  "d" => [["b", 2], ["c", 6], ["g", 4]],
  "g" => [["a", 6], ["d", 4]],
}

puts "### dijstra"
$result = dijkstra(node_data)
puts traverse($result["g"]).reverse

$ ruby dijkstra.rb
### dijstra
#### initialize
(a, [s,b,g], [5,2,6], false, 100000000)
(b, [s,a,c,d], [6,2,3,2], false, 100000000)
(c, [s,b,d], [2,3,6], false, 100000000)
(d, [b,c,g], [2,6,4], false, 100000000)
(g, [a,d], [6,4], false, 100000000)
(s, [a,b,c], [5,6,2], false, 0)
#### calculated
(a, [s,b,g], [5,2,6], true, 5)
(b, [s,a,c,d], [6,2,3,2], true, 5)
(c, [s,b,d], [2,3,6], true, 2)
(d, [b,c,g], [2,6,4], true, 7)
(g, [a,d], [6,4], true, 11)
(s, [a,b,c], [5,6,2], true, 0)
s
a
g