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 start 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(start) ⇒ Object

Use Dijkstra’s algorithm to find the shortest distances from the start vertex to each of the other vertices

Returns a hash of form { ‘start’ => 0, ‘a’ => 3, ‘b’ => 4 }, where result indicates the shortest distance from start to v



31
32
33
34
35
36
37
38
39
 
# File 'lib/dijkstra_graph/graph.rb', line 31

def shortest_distances(start)
  distances = Hash.new { Float::INFINITY } # Initial distances = Inf
  queue = initialize_queue(start)          # Begin at start 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(start, dest) ⇒ Object

Use Dijkstra’s algorithm to find the shortest path from the start 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



63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/dijkstra_graph/graph.rb', line 63

def shortest_path(start, dest)
  predecessors = {}                        # Initialize vertex predecessors
  distances = Hash.new { Float::INFINITY } # Initialize distances to Inf
  queue = initialize_queue(start)          # Initialize queue with start
  until queue.empty?
    v, distances[v] = queue.delete_min     # Visit next closest node
    return PathUtil.path_array(predecessors, start, dest) if v == dest
    update_paths_to_neighbours(v, predecessors, distances, queue)
  end
  [] # No path found from start to dest
end

#shortest_paths(start) ⇒ Object

Use Dijkstra’s algorithm to find the shortest paths from the start vertex to each of the other vertices

Returns a hash of form { ‘c’ => [‘a’, ‘b’, ‘c’] }, where result indicates the shortest path from start to v



46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/dijkstra_graph/graph.rb', line 46

def shortest_paths(start)
  predecessors = {}                        # Initialize vertex predecessors
  distances = Hash.new { Float::INFINITY } # Initialize distances to Inf
  queue = initialize_queue(start)          # Initialize queue with start
  until queue.empty?
    # Visit next closest vertex and update neighbours
    v, distances[v] = queue.delete_min
    update_paths_to_neighbours(v, predecessors, distances, queue)
  end
  PathUtil.path_arrays(predecessors, start)
end