Class: Knossos::Solver::Dijkstra

Inherits:
Object
  • Object
show all
Defined in:
lib/knossos/solver/dijkstra.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Dijkstra

Returns a new instance of Dijkstra.



4
5
6
 
# File 'lib/knossos/solver/dijkstra.rb', line 4

def initialize
  # nothing to do
end

Instance Method Details

#distances_from(start:) ⇒ Object 



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
# File 'lib/knossos/solver/dijkstra.rb', line 8

def distances_from(start:)
  frontier = [start]
  distances = Distances.new(root: start)

  while frontier.any?
    new_frontier = []

    frontier.each do |cell|
      cell.links.each do |linked_cell|
        next if distances[linked_cell]
        distances[linked_cell] = distances[cell] + 1
        new_frontier << linked_cell
      end
    end

    frontier = new_frontier
  end

  distances
end

#longest_path(distances:) ⇒ Object 



48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/knossos/solver/dijkstra.rb', line 48

def longest_path(distances:)
  # Find the cell that is furthest from any given starting cell. Then find
  # the cell that is furthest from that one. This is guaranteed to yield
  # the longest path in a perfect maze.

  new_start, _ = distances.max
  new_distances = distances_from(start: new_start)
  goal, _ = new_distances.max

  shortest_path(start: new_start, goal: goal, distances: new_distances)
end

#shortest_path(start:, goal:, distances:) ⇒ Object 



29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/knossos/solver/dijkstra.rb', line 29

def shortest_path(start:, goal:, distances:)
  current = goal

  path = Distances.new(root: start)
  path[current] = distances[current]

  until current == start
    current.links.each do |neighbor|
      if distances[neighbor] < distances[current]
        path[neighbor] = distances[neighbor]
        current = neighbor
        break
      end
    end
  end

  path
end