class Dijkstraruby::Graph

Attributes

vertices[R]

Public Class Methods

new(graph) click to toggle source
# File lib/dijkstraruby/graph.rb, line 9
def initialize(graph)
  initialize_vertices
  @edges = {}
  format_graph_values graph
  @dijkstra_source = nil
end

Public Instance Methods

dijkstra(source) click to toggle source
# 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) click to toggle source
# 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

Private Instance Methods

format_graph_values(graph) click to toggle source
# File lib/dijkstraruby/graph.rb, line 54
def format_graph_values(graph)
  graph.each do |(v1, v2, dist)|
    @vertices[v1].neighbours << v2
    @vertices[v2].neighbours << v1
    @edges[[v1, v2]] = @edges[[v2, v1]] = dist
  end
end
get_vertices_distances(vertex_values) click to toggle source
# File lib/dijkstraruby/graph.rb, line 42
def get_vertices_distances(vertex_values)
  initial_vertice = vertex_values.min_by { |vertex| vertex.distance }
  initial_vertice.neighbours.each do |v|
    vv = @vertices[v]
    alt = initial_vertice.distance + @edges[[initial_vertice.name, v]]
    if vertex_values.include?(vv) && alt < vv.distance
      vv.change_distance_and_previous alt, initial_vertice
    end
  end
  initial_vertice
end
initialize_vertices() click to toggle source
# File lib/dijkstraruby/graph.rb, line 62
def initialize_vertices
  @vertices = Hash.new { |h, k| h[k] = Vertex.new(k, [], Float::INFINITY) }
end