Class: Dijkstra

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

Instance Method Summary collapse

Constructor Details

#initialize(graph, source_vertex) ⇒ Dijkstra

Returns a new instance of Dijkstra.



4
5
6
7
8
9
10
11
12
 
# File 'lib/dijkstra.rb', line 4

def initialize(graph, source_vertex)
  @graph = graph
  @vertices = @graph.vertices
  @source_vertex = source_vertex
  @path_to = {}
  @distance_to = {}
  @pq = PriorityQueue.new
  compute_shortest_path
end

Instance Method Details

#shortest_path_to(vertex) ⇒ Object 



14
15
16
17
18
19
20
21
22
23
 
# File 'lib/dijkstra.rb', line 14

def shortest_path_to(vertex)
  return [] unless reachable?(vertex)
  return [] if @distance_to[vertex] == 0
  path = []
  while vertex != @source_vertex
    path.unshift(vertex)
    vertex = @path_to[vertex]
  end
  path.unshift(@source_vertex)
end