http://okajima.air-nifty.com/b/2010/01/post-abc6.html

maze.rb

def main
  maze, start, goal = read(ARGF)
  path = start.dijkstra
  write(maze, path, goal)
end

def read(input)
  start = nil
  goal = nil
  prev = []
  maze = input.to_a.map{|line| line.strip.split('')}.map do |line|
    left = nil
    prev = line.zip(prev).map do |c,up|
      if c != '*'
        c = Node.new(c)
        start = c if c.s == 'S'
        goal = c if c.s == 'G'
        c.connect(left) if left.is_a?(Node)
        c.connect(up) if up.is_a?(Node)
      end
      left = c
    end
  end
  return [maze, start, goal]
end

def write(maze, path, goal)
  p = path[goal]
  while p
    p.s.sub!(' ', '$')
    p = path[p]
  end
  maze.each{|line| puts(line.map{|c| c.to_s}.join(''))}
end

class Node
  attr_accessor :next, :s
  def initialize(s) @s = s; @next = [] end
  def to_s; return @s.to_s end
  def connect(other) @next << other; other.next << self end
  def dijkstra
    dist = Distance.new
    dist[self] = 0
    q = PQueue.new(proc{|x| dist[x]})
    q << self
    done = {}
    path = {}
    while q.size > 0
      u = q.pop()
      next if done[u]
      done[u] = true
      u.next.each do |v|
        unless done[v]
          if dist[v] > dist[u].succ
            dist[v] = dist[u].succ
            path[v] = u
          end
          q << v
        end
      end
    end
    return path
  end
end

class Distance
  def initialize; @dist = {} end
  def [](x) return @dist[x] || Float::MAX end
  def []=(x,v) @dist[x] = v end
end

class PQueue # priority queue
  def initialize(d) @a = []; @d = d end
  def <<(v) (@a << v).sort!{|a,b| @d.call(a) <=> @d.call(b)} end
  def size; return @a.length end
  def pop; return @a.shift end
end

main