Dijkstra (Fast!)

• README: https://github.com/david-mccullars/dijkstra_fast
• Documentation: http://www.rubydoc.info/github/david-mccullars/dijkstra_fast
• Bug Reports: https://github.com/david-mccullars/dijkstra_fast/issues

Status

Description

Dijkstra is a commonly used algorithm for finding the shortest path/distance between two items in an interconnected collection of items (such as a graph or network).

Features

• Native implementation of Dijkstra's algorithm intended for use on large, typically sparse graphs.
• Allows for calculating shortest distance without requiring all nodes/edges to be produced. (In many applications doing this can be more expensive than Dijkstra's algorithm itself - or even impractical.)
• Can be used in one of three ways:
  • Method 1: Use an instance of DijkstraFast::Graph by adding edges to it.
  • Method 2: Add shortest_path and shortest_distance methods to an existing class by including the DijkstraFast::ShortestPath module.
  • Method 3: Call DijkstraFast::ShortestPath.shortest_path or DijkstraFast::ShortestPath.shortest_distance directly when the source and dest objects know how to find "connected" items via some method.

Installation

gem install dijkstra_fast

Requirements

• Ruby 3.0 or higher

Usage

Method 1: Use DijkstraFast::Graph

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

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

distance

=> 7

Method 2: Include DijkstraFast::ShortestPath

class MyNetwork
  include DijkstraFast::ShortestPath

  def connections(source)
    case source
    when "A"
      yield "B", 3
      yield "C", 8
    when "B"
      yield "C" # Default distance 1
    end
  end
end

distance, path = MyNetwork.new.shortest_path("A", "C")
path

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

distance

=> 4

Method 3: Call DijkstraFast.shortest_path or DijkstraFast.shortest_distance

Node = Struct.new(:label) do
  def connections
    case label
    when "A"
      yield Node.new("B"), 5
      yield Node.new("C"), 8
    when "B"
      yield Node.new("C"), 2
    end
  end
end

a = Node.new("A")
b = Node.new("B")
c = Node.new("C")

distance, path = DijkstraFast.shortest_path(a, c)
path.map(&:label)

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

distance

=> 7

Additional Notes

• When using arbitrary Ruby objects as graph nodes, it is important to ensure that Object#hash and Object#eql? are properly implemented so that two instances which are logically the same will be considered as the same node. Under the hood, this gem creates a bi-directional mapping between nodes and an auto-incrementing integer id so that Ruby objects do not have to be passed into the internals of the native implementation; doing so would risk problems with garbage collection and is otherwise frowned upon when implementing native extensions.
• All shortest_path and shortest_distance methods provide an optional progress named argument which (when set to anything truthy) will provide progress as the algorithm proceeds. The default implementation uses the progressbar gem, but this is not required.
• The maximum number of items that can be handled by this implementation is determined by the size of unsigned long which is compiler dependent. On many machines this can be 18,446,744,073,709,551,615 (2^64 – 1). A RuntimeError will be thrown if this is surpassed; if so, congratulations on being bad ass!
• A priority queue is used within the native Dijkstra implemenation to maintain the next shortest path to consider within the algorithm's main loop. It is possible that switching to a Fibonacci heap might improve performance.

License

MIT. See the LICENSE file.

References

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw–Hill. pp. 595–601. ISBN 0-262-03293-7.

Knuth, D.E. (1977). "A Generalization of Dijkstra's Algorithm". Information Processing Letters. 6 (1): 1–5. doi:10.1016/0020-0190(77)90002-3.