Dijkstra search implemented in Ruby

a.rb

MAP = "
*************
* S         *
* ** * ***  *
**   *  *  **
*  **** * ***
*  * ** * ***
*  * ** * ***
*  * *  *G  *
*           *
*************
".lines.drop(1).map{|l| l.chomp.chars}

MAP_W = MAP.first.length
MAP_H = MAP.length
MAP.each.with_index do |row, y|
  row.each.with_index do |ch, x|
    if ch == "G"
      GOAL_X = x
      GOAL_Y = y
    elsif ch == "S"
      START_X = x
      START_Y = y
    end
  end
end

def clone_map(m)
  m.map{|row| row.dup}
end

def dump(m)
  m.each do |row|
    row.each do |ch|
      print ch, " "
    end
    puts
  end
end

def passable?(m, x, y)
  m[y][x] != "*"
end

DIRS = [
  # dx dy
  # south   north    west      east
  [0, +1], [0, -1], [-1, 0], [+1, 0]
]
def dijkstra(m, start_x, start_y)
  dist = {[start_x, start_y] => 0}
  previous = {}
  q = []

  m.each.with_index do |row, y|
    row.each.with_index do |ch, x|
      next unless passable?(m, x, y)

      if [x, y] != [start_x, start_y]
        dist[[x,y]] = Float::INFINITY
        previous[[x,y]] = nil
      end
      q.push([x,y])
    end
  end

  until q.empty?
    u = q.min_by{|v| dist[v]}
    q.delete(u)

    DIRS.each do |dx, dy|
      v = [u[0]+dx, u[1]+dy]
      next unless passable?(m, v[0], v[1])

      alt = dist[u] + 1  # 1: length
      if alt < dist[v]
        dist[v] = alt
        previous[v] = u
      end
    end
  end
  return dist, previous
end

def dump_dist(m, dist)
  m.each.with_index do |row, y|
    row.each.with_index do |ch, x|
      if (d = dist[[x,y]])
        print format("%02d", d)
      else
        print ch, " "
      end
    end
    puts
  end
end

def dump_path(m, previous)
  mm = clone_map(m)

  x, y = GOAL_X, GOAL_Y
  loop do
    x, y = *previous[[x,y]]

    break if [x,y] == [START_X, START_Y]

    mm[y][x] = "@"
  end

  dump(mm)
end

dump(MAP)

p w: MAP_W, h: MAP_H, gx: GOAL_X, gy: GOAL_Y

dist, previous = dijkstra(MAP, 2, 1)
dump_dist(MAP, dist)
dump_path(MAP, previous)

p dist: dist, previous: previous