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