class DijkstraGraph::Graph
A graph supporting Dijkstra's shortest path algorithm
Edges are stored in an adjacency list for O(1) access to the neighbours list of a given vertex.
Vertices 'to-visit' are stored in a priority queue that uses a Fibonacci heap to give O(1) insert, amortized O(1) decrease_priority, and amortized O(log n) delete_min. Priority represents path distance from the source vertex.
The shortest distances found so far to each vertex are stored in a simple hash which gives O(1) read/write.
Public Class Methods
Initialize graph edges
# File lib/dijkstra_graph/graph.rb, line 22 def initialize super end
Public Instance Methods
Use Dijkstra's algorithm to find the shortest distances from the source vertex to each of the other vertices
Returns a hash of form { 'source' => 0, 'a' => 3, 'b' => 4 }, where result indicates the shortest distance from source to v
# File lib/dijkstra_graph/graph.rb, line 31 def shortest_distances(source) distances = Hash.new { Float::INFINITY } # Initial distances = Inf queue = initialize_queue(source) # Begin at source node until queue.empty? v, distances[v] = queue.delete_min # Visit next closest vertex update_distances_to_neighbours(v, distances, queue) # Update neighbours end distances end
Use Dijkstra's algorithm to find the shortest path from the source vertex to the destination vertex
Returns an array of vertices along the shortest path of form ['a', 'b', 'c'], or [] if no such path exists
# File lib/dijkstra_graph/graph.rb, line 82 def shortest_path(source, dest) predecessors = {} # Initialize vertex predecessors distances = Hash.new { Float::INFINITY } # Initialize distances to Inf queue = initialize_queue(source) # Initialize queue with source until queue.empty? v, distances[v] = queue.delete_min # Visit next closest node return PathUtil.path_array(predecessors, source, dest) if v == dest update_paths_to_neighbours(v, distances, queue, predecessors) end [] # No path found from source to dest end
Use Dijkstra's algorithm to find the shortest paths from the source vertex to each of the other vertices
Returns a hash of form { 'c' => ['a', 'b', 'c'] }, where result indicates the shortest path from source to v
# File lib/dijkstra_graph/graph.rb, line 46 def shortest_paths(source) predecessors = {} # Initialize vertex predecessors distances = Hash.new { Float::INFINITY } # Initialize distances to Inf queue = initialize_queue(source) # Initialize queue with source until queue.empty? # Visit next closest vertex and update neighbours v, distances[v] = queue.delete_min update_paths_to_neighbours(v, distances, queue, predecessors) end PathUtil.path_arrays(predecessors, source) end
Use Dijkstra's algorithm to find the shortest paths from the source vertex to vertices within a given radius
Returns a hash of form { 'c' => ['a', 'b', 'c'] }, where result indicates the shortest path from source to v
# File lib/dijkstra_graph/graph.rb, line 63 def shortest_paths_in_radius(source, radius) predecessors = {} # Initialize vertex predecessors distances = Hash.new { Float::INFINITY } # Initialize distances to Inf queue = initialize_queue(source) # Initialize queue with source until queue.empty? # Visit next closest vertex and update neighbours v, distance = queue.delete_min return PathUtil.path_arrays(predecessors, source) if distance > radius distances[v] = distance update_neighbours_in_radius(v, distances, queue, predecessors, radius) end PathUtil.path_arrays(predecessors, source) end
Private Instance Methods
Initialize priority queue with source vertex at distance = 0
# File lib/dijkstra_graph/graph.rb, line 97 def initialize_queue(source_vertex) queue = PriorityQueue.new queue[source_vertex] = 0 queue end
Update shortest distance to vertex
# File lib/dijkstra_graph/graph.rb, line 135 def update_distance(vertex, distance, params) params[:queue][vertex] = params[:distances][vertex] = distance end
Update distances to neighbours of v and queue changed neighbours
# File lib/dijkstra_graph/graph.rb, line 104 def update_distances_to_neighbours(v, distances, queue) update_neighbours(v, distances, method(:update_distance), distances: distances, queue: queue) end
Apply given method to each neighbour we find a shorter path to
# File lib/dijkstra_graph/graph.rb, line 124 def update_neighbours(v, distances, update_method, update_params) distance_v = distances[v] get_adjacent_vertices(v).each do |w| distance_through_v = distance_v + get_edge_weight(v, w) if distance_through_v < distances[w] update_method.call(w, distance_through_v, update_params) end end end
Update paths to neighbours of v in radius and queue changed neighbours
# File lib/dijkstra_graph/graph.rb, line 117 def update_neighbours_in_radius(v, distances, queue, predecessors, radius) update_neighbours(v, distances, method(:update_path), distances: distances, queue: queue, radius: radius, predecessors: predecessors, predecessor: v) end
Update shortest path to vertex
# File lib/dijkstra_graph/graph.rb, line 140 def update_path(vertex, distance, params) return if params[:radius] && distance > params[:radius] update_distance(vertex, distance, params) params[:predecessors][vertex] = params[:predecessor] end
Update paths to neighbours of v and queue changed neighbours
# File lib/dijkstra_graph/graph.rb, line 110 def update_paths_to_neighbours(v, distances, queue, predecessors) update_neighbours(v, distances, method(:update_path), distances: distances, queue: queue, predecessors: predecessors, predecessor: v) end