O'Reilly logo

Mazes for Programmers by Jamis Buck

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Implementing a Cost-Aware Dikstra’s Algorithm

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.

Put the following in weighted_cell.rb.

weighted_cell.rb
Line 1 
require ​'cell'
class​ WeightedCell < Cell
attr_accessor :weight
def​ initialize(row, column)
super​(row, column)
@weight = 1
end
10 
def​ distances
weights = Distances.new(self)
pending = [ self ]
15 
while

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required