class RGL::DijkstraAlgorithm
This class implements {Graph#dijkstra_shortest_path} and {Graph#dijkstra_shortest_paths}
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 19 def initialize(graph, edge_weights_map, visitor, distance_combinator = nil) 20 @graph = graph 21 @edge_weights_map = build_edge_weights_map(edge_weights_map) 22 @visitor = visitor 23 @distance_combinator = distance_combinator || DEFAULT_DISTANCE_COMBINATOR 24 end
Public Instance Methods
Finds the shortest path from the source to every other vertex.
# File lib/rgl/dijkstra.rb 48 def find_shortest_paths(source) 49 init(source) 50 relax_edges 51 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 30 def shortest_path(source, target) 31 init(source) 32 relax_edges(target, true) 33 PathBuilder.new(source, @visitor.parents_map).path(target) 34 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 41 def shortest_paths(source) 42 find_shortest_paths(source) 43 PathBuilder.new(source, @visitor.parents_map).paths(@graph.vertices) 44 end
Private Instance Methods
# File lib/rgl/dijkstra.rb 101 def build_edge_weights_map(edge_weights_map) 102 edge_weights_map.is_a?(EdgePropertiesMap) ? edge_weights_map : NonNegativeEdgePropertiesMap.new(edge_weights_map, @graph.directed?) 103 end
# File lib/rgl/dijkstra.rb 55 def init(source) 56 @visitor.set_source(source) 57 58 @queue = PairingHeap::MinPriorityQueue.new 59 @queue.push(source, 0) 60 end
# File lib/rgl/dijkstra.rb 79 def relax_edge(u, v) 80 @visitor.handle_examine_edge(u, v) 81 82 new_v_distance = @distance_combinator.call(@visitor.distance_map[u], @edge_weights_map.edge_property(u, v)) 83 84 if new_v_distance < @visitor.distance_map[v] 85 @visitor.distance_map[v] = new_v_distance 86 @visitor.parents_map[v] = u 87 88 if @visitor.color_map[v] == :WHITE 89 @visitor.color_map[v] = :GRAY 90 @queue.push(v, new_v_distance) 91 elsif @visitor.color_map[v] == :GRAY 92 @queue.decrease_key(v, new_v_distance) 93 end 94 95 @visitor.handle_edge_relaxed(u, v) 96 else 97 @visitor.handle_edge_not_relaxed(u, v) 98 end 99 end
# File lib/rgl/dijkstra.rb 62 def relax_edges(target = nil, break_on_target = false) 63 until @queue.empty? 64 u = @queue.pop 65 66 break if break_on_target && u == target 67 68 @visitor.handle_examine_vertex(u) 69 70 @graph.each_adjacent(u) do |v| 71 relax_edge(u, v) unless @visitor.finished_vertex?(v) 72 end 73 74 @visitor.color_map[u] = :BLACK 75 @visitor.handle_finish_vertex(u) 76 end 77 end