class RGL::DijkstraAlgorithm
Constants
- DEFAULT_DISTANCE_COMBINATOR
Distance combinator is a lambda that accepts the distance (usually from the source) to vertex u and the weight of the edge connecting vertex u to another vertex v and returns the distance to vertex v if it's reached through the vertex u. By default, the distance to vertex u and the edge's weight are summed.
Public Class Methods
Initializes Dijkstra's algorithm for a graph with provided edges weights map.
# File lib/rgl/dijkstra.rb, line 18 def initialize(graph, edge_weights_map, visitor, distance_combinator = nil) @graph = graph @edge_weights_map = build_edge_weights_map(edge_weights_map) @visitor = visitor @distance_combinator = distance_combinator || DEFAULT_DISTANCE_COMBINATOR end
Public Instance Methods
Finds the shortest path from the source to every other vertex.
# File lib/rgl/dijkstra.rb, line 47 def find_shortest_paths(source) init(source) relax_edges end
Finds the shortest path from the source to the target in the graph.
Returns the shortest path, if it exists, as an Array of vertices. Otherwise, returns nil.
# File lib/rgl/dijkstra.rb, line 29 def shortest_path(source, target) init(source) relax_edges(target, true) PathBuilder.new(source, @visitor.parents_map).path(target) end
Finds the shortest path form the source to every other vertex of the graph and builds shortest paths map.
Returns the shortest paths map that contains the shortest path (if it exists) from the source to any vertex of the graph.
# File lib/rgl/dijkstra.rb, line 40 def shortest_paths(source) find_shortest_paths(source) PathBuilder.new(source, @visitor.parents_map).paths(@graph.vertices) end
Private Instance Methods
# File lib/rgl/dijkstra.rb, line 100 def build_edge_weights_map(edge_weights_map) edge_weights_map.is_a?(EdgePropertiesMap) ? edge_weights_map : NonNegativeEdgePropertiesMap.new(edge_weights_map, @graph.directed?) end
# File lib/rgl/dijkstra.rb, line 54 def init(source) @visitor.set_source(source) @queue = MinPriorityQueue.new @queue.push(source, 0) end
# File lib/rgl/dijkstra.rb, line 78 def relax_edge(u, v) @visitor.handle_examine_edge(u, v) new_v_distance = @distance_combinator.call(@visitor.distance_map[u], @edge_weights_map.edge_property(u, v)) if new_v_distance < @visitor.distance_map[v] @visitor.distance_map[v] = new_v_distance @visitor.parents_map[v] = u if @visitor.color_map[v] == :WHITE @visitor.color_map[v] = :GRAY @queue.push(v, new_v_distance) elsif @visitor.color_map[v] == :GRAY @queue.decrease_key(v, new_v_distance) end @visitor.handle_edge_relaxed(u, v) else @visitor.handle_edge_not_relaxed(u, v) end end
# File lib/rgl/dijkstra.rb, line 61 def relax_edges(target = nil, break_on_target = false) until @queue.empty? u = @queue.pop break if break_on_target && u == target @visitor.handle_examine_vertex(u) @graph.each_adjacent(u) do |v| relax_edge(u, v) unless @visitor.finished_vertex?(v) end @visitor.color_map[u] = :BLACK @visitor.handle_finish_vertex(u) end end