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

new() click to toggle source

Initialize graph edges

Calls superclass method
# File lib/dijkstra_graph/graph.rb, line 22
def initialize
  super
end

Public Instance Methods

shortest_distances(source) click to toggle source

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
shortest_path(source, dest) click to toggle source

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

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
shortest_paths_in_radius(source, radius) click to toggle source

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_queue(source_vertex) click to toggle source

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_distance(vertex, distance, params) click to toggle source

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(v, distances, queue) click to toggle source

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
update_neighbours(v, distances, update_method, update_params) click to toggle source

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_neighbours_in_radius(v, distances, queue, predecessors, radius) click to toggle source

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_path(vertex, distance, params) click to toggle source

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(v, distances, queue, predecessors) click to toggle source

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