Class: DijkstraGraph::Graph

Inherits:
WeightedGraph::PositiveWeightedGraph
  • Object
show all
Defined in:
lib/dijkstra_graph/graph.rb

Overview

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.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Initialize graph edges



22
23
24
 
# File 'lib/dijkstra_graph/graph.rb', line 22

def initialize
  super
end

Instance Method Details

#shortest_distances(source) ⇒ Object

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



31
32
33
34
35
36
37
38
39
 
# 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) ⇒ Object

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



82
83
84
85
86
87
88
89
90
91
92
 
# 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) ⇒ Object

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



46
47
48
49
50
51
52
53
54
55
56
 
# 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) ⇒ Object

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



63
64
65
66
67
68
69
70
71
72
73
74
75
 
# 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