Skip to content

Instantly share code, notes, and snippets.

@melborne
Created January 21, 2010 08:18
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save melborne/282664 to your computer and use it in GitHub Desktop.
Dijkstra method
#!/usr/bin/env ruby -wKU
# -*- encoding:utf-8 -*-
class Node
attr_accessor :id, :edges, :cost, :done, :from
def initialize(id, edges=[], cost=nil, done=false)
@id, @edges, @cost, @done = id, edges, cost, done
end
end
class Edge
attr_reader :cost, :nid
def initialize(cost, nid)
@cost, @nid = cost, nid
end
end
class Graph
def initialize(data)
@nodes =
data.map do |id, edges|
edges.map! { |edge| Edge.new(*edge) }
Node.new(id, edges)
end
end
def cost(nid, sid)
dijkstra(sid)
@nodes.find { |node| node.id == nid }.cost
end
def route(sid, gid)
dijkstra(sid)
base = @nodes.find { |node| node.id == gid }
res = [base]
while base = @nodes.find { |node| node.id == base.from }
res << base
end
res
end
def print_route(sid, gid)
res = route(sid, gid)
puts res.reverse.map { |node| "#{node.id}(#{node.cost})" }.join(" -> ")
end
private
def dijkstra(sid)
@nodes.each do |node|
node.cost = node.id == sid ? 0 : nil
node.done = false
node.from = nil
end
loop do
done_node = nil
@nodes.each do |node|
next if node.done or node.cost.nil?
done_node = node if done_node.nil? or node.cost < done_node.cost
end
break unless done_node
done_node.done = true
done_node.edges.each do |edge|
to = @nodes.find{ |node| node.id == edge.nid }
cost = done_node.cost + edge.cost
from = done_node.id
if to.cost.nil? || cost < to.cost
to.cost = cost
to.from = from
end
end
end
end
end
if __FILE__ == $0
data = {
:s => [[5, :a], [4, :b], [2, :c]],
:a => [[5, :s], [2, :b], [6, :g]],
:b => [[4, :s], [2, :a], [3, :c], [2, :d]],
:c => [[2, :s], [3, :b], [6, :d]],
:d => [[2, :b], [6, :c], [4, :g]],
:g => [[6, :a], [4, :d]]
}
g = Graph.new(data)
g.print_route(:s, :g)
puts g.cost(:d, :s)
g.print_route(:a, :c)
end
#!/usr/bin/env ruby -wKU
# -*- encoding:utf-8 -*-
require_relative "dijkstra"
maze = DATA.readlines.map { |line| line.chomp.split(//) }
nodes = {}
maze.each.with_index do |line, y|
line.each.with_index do |data, x|
next if data == '*'
id = data.match(/\w/) ? $& : "#{y}_#{x}"
edges =
[[-1, 0], [1, 0], [0, -1], [0, 1]].inject([]) do |mem, (_y, _x)|
_x += x; _y += y
case maze[_y][_x]
when /\w/ then mem << $&
when /\s/ then mem << "#{_y}_#{_x}"
else mem
end
end.map { |nid| [1, nid] }
nodes[id] = edges
end
end
g = Graph.new(nodes)
route = g.route('S', 'G')
maze.each_with_index do |line, y|
line.each_with_index do |data, x|
print route.find { |pos| pos.id == "#{y}_#{x}" } ? '$' : data
end
print "\n"
end
__END__
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment