Class: DijkstraFast::Graph

Inherits:
Object
  • Object
show all
Includes:
ShortestPath
Defined in:
lib/dijkstra_fast/graph.rb

Overview

Dijkstra's algorithm finds the shortest "distance" between two items within a collection. For any two items within that collection that are "connected" there should be an associated "distance" between them. We can represent this collection of items as nodes in a directed graph, and we can represent the associated connections as weighted edges.

= Example

graph = DijkstraFast::Graph.new graph.add("A", "B", distance: 5) graph.add("A", "C", distance: 8) graph.add("B", "C", distance: 2) best_path = graph.shortest_path("A", "C") best_path.path

=> ["A", "B", "C"]

best_path.distance

=> 7

Instance Method Summary collapse

Methods included from ShortestPath

#shortest_distance, #shortest_path

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



29
30
31
 
# File 'lib/dijkstra_fast/graph.rb', line 29

def initialize
  @edges = {}
end

Instance Method Details

#add(source, dest, distance: 1) ⇒ nil

Adds a weighted edge to the graph. This represents a possible path from the source item to the destination item with corresponding "distance."

Parameters:

  • source (Object) —

    Any Ruby object that represents the source item

  • dest (Object) —

    Any Ruby object that represents the destination item

  • distance (Integer) (defaults to: 1) —

    Optional distance between source and destination. If not provided, a default distance of 1 is used.

Returns:

  • (nil) 


40
41
42
43
44
45
 
# File 'lib/dijkstra_fast/graph.rb', line 40

def add(source, dest, distance: 1)
  return if source == dest

  @edges[source] ||= []
  @edges[source] << [dest, distance]
end

#connections(source, &block) ⇒ Object 



47
48
49
50
 
# File 'lib/dijkstra_fast/graph.rb', line 47

def connections(source, &block)
  @edges[source]&.each(&block)
  nil
end