Class: Dijkstraruby::Graph

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ Graph

Returns a new instance of Graph.



9
10
11
12
13
14
 
# File 'lib/dijkstraruby/graph.rb', line 9

def initialize(graph)
  initialize_vertices
  @edges = {}
  format_graph_values graph
  @dijkstra_source = nil
end

Instance Attribute Details

#vertices ⇒ Object (readonly)

Returns the value of attribute vertices.



7
8
9
 
# File 'lib/dijkstraruby/graph.rb', line 7

def vertices
  @vertices
end

Instance Method Details

#dijkstra(source) ⇒ Object 



16
17
18
19
20
21
22
23
24
25
26
27
 
# File 'lib/dijkstraruby/graph.rb', line 16

def dijkstra(source)
  vertex_values = @vertices.values
  @vertices[source].set_zero_for_initial_vertice

  until vertex_values.empty?
    initial_vertice = get_vertices_distances vertex_values
    break if initial_vertice.distance == Float::INFINITY
    vertex_values.delete(initial_vertice)
  end

  @dijkstra_source = source
end

#shortest_path(start, finish) ⇒ Object 



29
30
31
32
33
34
35
36
37
38
 
# File 'lib/dijkstraruby/graph.rb', line 29

def shortest_path(start, finish)
  dijkstra(start) unless @dijkstra_source == start
  path = []
  first_array_element = finish
  while first_array_element
    path.unshift(first_array_element)
    first_array_element = @vertices[first_array_element].prev_vertice
  end
  [path, @vertices[finish].distance]
end