- 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
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).
- 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::Graphby adding edges to it.
- Method 2: Add
shortest_distancemethods to an existing class by including the
- Method 3: Call
DijkstraFast::ShortestPath.shortest_distancedirectly when the
destobjects know how to find "connected" items via some method.
- Method 1: Use an instance of
gem install dijkstra_fast
- Ruby 3.0 or higher
Method 1: Use
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
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
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
- 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.
shortest_distancemethods provide an optional
progressnamed 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 longwhich 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.
MIT. See the
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.