Ruby implementation of Dijkstra's algorithm. http://en.wikipedia.org/wiki/Dijkstra's_algorithm

pathfinder.rb

map = <<-EOS
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . X X X X X X X . .
. . . . . . . X . . . . . X . .
. . . . . . . X . . . . . . . .
. . . . . . . X . . . . . X . .
. . . . . . . X . . S . . X . .
. . . . . . . X . . . . . X . .
. . . . . . . X X X X X X X . .
. . . . . . . . . . . . . . . .
. . E . X . . . . . . . . . . .
. . . . X . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .

EOS

class Pathfinder
  def update
    puts "\n" * 5
    puts Cell.draw_map
    sleep 0.5
  end
  
  def parse_map(str)
    lines = str.gsub(" ", "").split("\n")
    lines.delete_if {|line| line == ""}
    lines.each.with_index do |line, y|
      line.chars.each.with_index do |cell, x|
        Cell.new(cell, x, y)
      end
    end
  end
  
  def compute
    done = nil
    current = [Cell.start_cell]
    Cell.start_cell.steps = 0
    250.times do |i|
      i2 = i + 1
      candidates = []
      current.each do |c|
        c.available.each do |w|
          if w.open?
            if !w.steps || w.steps > i2
              w.steps = i2
              candidates << w
              if w.end?
                done = true
                break
              end
            end
          end
          break if !done.nil?
        end
        break if !done.nil?
      end
      break if !done.nil?
      if candidates.length > 0
        current = candidates
        update
      else
        done = false
        break
      end
    end
    done
  end
  
  def solve
    if compute
      Cell.mark_path(trace_back)
      update
    end
  end
  
  def trace_back
    r = [c = Cell.end_cell]
    until c.start?
      a = c.available.select {|b| b.steps && b.steps == c.steps - 1}
      c = a[rand a.length]
      r << c
    end
    r
  end
  
  class Cell
    attr_accessor :steps
    @@map = []
    @@max_step = 0
    @@start_cell = nil
    @@end_cell = nil
    
    def self.<=>(other)
      self.steps <=> other.steps
    end
    
    def self.end_cell
      return @@end_cell if @@end_cell
      @@map.detect do |l|
        l.detect do |c|
          @@end_cell = c if c.end?
        end
      end
      @@end_cell
    end
    
    def self.start_cell
      return @@start_cell if @@start_cell
      @@map.detect do |l|
        l.detect do |c|
          @@start_cell = c if c.start?
        end
      end
      @@start_cell
    end
    
    def self.mark_path(solution)
      @@map.each do |line|
        line.each do |cell|
          unless solution.include?(cell)
            cell.steps = nil
          end
        end
      end
    end
    
    def initialize(str, x, y)
      @x = x
      @y = y
      @s = str
      @start = false
      @end = false
      case str
      when "."
        @open = true
      when "X"
        @open = false
      when "S"
        @open = true
        @start = true
      when "E"
        @open = true
        @end = true
      end
      @@map[y] ||= []
      @@map[y][x] = self
    end
    
    def inspect
      atrs = instance_variables.map {|v| "#{v}=#{instance_variable_get(v).inspect}"}.join(", ")
      "<#{self.class.name}:#{self.hash} #{atrs}>"
    end
    
    def self.max_step
      @@max_step
    end
    
    def steps=(other)
      @@max_step = other if other && other > @@max_step
      @steps = other
    end
    
    def self.draw_map
      m = max_step.to_s.length + 1
      @@map.map do |line|
        line.map(&:to_s).map {|s| sprintf "%-#{m}s", s}.join
        #.join(" " * (max_step.to_s.length + 1))
      end
      .join("\n")
    end
    
    def to_s
      if start? || end?
        @s
      else
        @steps || @s
      end
    end
    
    def open?
      @open
    end
    
    def start?
      @start
    end
    
    def end?
      @end
    end
    
    def available
      [above, below, left, right].select {|v| v}
    end
    
    def above
      if @y > 0
        @@map[@y - 1][@x]
      else
        false
      end
    end
    
    def below
      if @y < @@map.length - 1
        @@map[@y + 1][@x]
      else
        false
      end
    end
    
    def left
      if @x > 0
        @@map[@y][@x - 1]
      else
        false
      end
    end
    
    def right
      if @x < @@map.first.length - 1
        @@map[@y][@x + 1]
      else
        false
      end
    end
    
    def self.map
      @@map
    end
  end
  
end

p = Pathfinder.new
p.parse_map(map)
p.solve