Class: Abuelo::Algorithms::Dijkstra

Inherits:
Object
  • Object
show all
Defined in:
lib/abuelo/algorithms/dijkstra.rb

Overview

Class Dijkstra implements Dijkstra’s algorithm for finding shortest paths between nodes in a graph.

See en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Possible improvement: use a priority queue to improve runtime.

Author:

Instance Method Summary collapse

Constructor Details

#initialize(graph, start_node) ⇒ Dijkstra

Returns a new instance of Dijkstra.

Parameters:

Raises:



21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/abuelo/algorithms/dijkstra.rb', line 21

def initialize(graph, start_node)
  if !start_node.is_a?(Abuelo::Node)
    raise Abuelo::Exceptions::NoNodeError.new('start_node is not a Abuelo::Node')
  end

  @graph          = graph
  @start_node     = start_node
  @distances      = {}
  @previous_nodes = {}
  init
  process
end

Instance Method Details

#shortest_distance_to(node) ⇒ Numeric?

Calculates the shortest distance from the start_node to the given node.

Parameters:

Returns:

  • (Numeric, nil) —

    the distance to the node or nil if node is unreachable



41
42
43
 
# File 'lib/abuelo/algorithms/dijkstra.rb', line 41

def shortest_distance_to(node)
  @distances[node]
end

#shortest_path_to(node) ⇒ Array<Abuelo::Node>?

Calculates the shortest path from the start_node to the given node.

Parameters:

Returns:

  • (Array<Abuelo::Node>, nil) —

    list of nodes from start_node to the given node that are a possible solution for the shortest path. Nil if node is unreachable.



53
54
55
56
57
58
59
60
61
62
 
# File 'lib/abuelo/algorithms/dijkstra.rb', line 53

def shortest_path_to(node)
  return nil if @previous_nodes[node].nil?

  nodes = [node]
  while previous_node = @previous_nodes[nodes[0]] do
    nodes.unshift(previous_node)
  end

  nodes
end