Mazes for Programmers/

...

/

Implementing a Cost-Aware Dijkstra's Algorithm

Implementing a Cost-Aware Dijkstra's Algorithm

Learn how to implement a cost-effective Dijkstra's algorithm on the mazes using Ruby.

We'll cover the following...

The WeightedCell class

In this lesson, we're going to apply Dijkstra's algorithm to the mazes by creating a few mazes with some lava pits. To make this work in code, we need two things: a cell that can be assigned a weight and a grid composed of these weighted cells.

The cell is straightforward. We’re just going to subclass Cell and add weight information to it. Also, since our Dijkstra’s algorithm was implemented on Cell, we put our updated implementation in the subclass, too, by overriding the original distances method.

Press + to interact
require 'cell'
class WeightedCell < Cell
  attr_accessor :weight
  def initialize(row, column)
    super(row, column)
    @weight = 1
  end
  def distances
    weights = Distances.new(self)
    pending = [ self ] 
    while pending.any? 
      cell = pending.sort_by { |c| weights[c] }.first 
      pending.delete(cell)
      cell.links.each do |neighbor| 
        total_weight = weights[cell] + neighbor.weight 
        if !weights[neighbor] || total_weight < weights[neighbor] 
          pending << neighbor
          weights[neighbor] = total_weight
        end
      end
    end
    weights
  end
end

Code explanation

Lines 6–9: Our constructor just extends the previous one by setting the default cell weight to 1.

Line 13: The new distances method is of particular interest here. As before, we use our Distances class to track the cost of each cell, but instead of having a frontier set, we now have a pending set, which tracks which cells have yet to be processed. We initialize pending to an array containing just self—the cell that we’re asking to compute ...