Dijkstra's algorithm, conceived by computer scientist Edsger Dijkstra, is a graph search algorithm that solves in single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree.
gem install dijkstra
require 'dijkstra'
# In this context we have 9 edges or paths.
r = [[1, 2, 1],
[1, 3, 9],
[1, 5, 3],
[2, 4, 3],
[2, 3, 7],
[4, 3, 2],
[4, 1, 1],
[5, 2, 4],
[5, 4, 2]]
start_point = 1 # starting node
end_point = 3 # arrival node
ob = Dijkstra.new(start_point, end_point, r)
puts "Cost = #{ob.cost}"
puts "Shortest Path from #{start_point} to #{end_point} = #{ob.shortest_path}"
ob.write_to_file('shortestpath.out')
=> shortestpath.out =>
Cost -> 6
Shortest Path -> [1, 2, 4, 3]
You can use any kind of element as node, not only numbers. If returned cost is Infinity, and returned shortest_path is the starting node, then there is no Path that connects starting node and arrival node.
$ git clone git://github.com/oscartanner/dijkstra.gem.git
$ cd dijkstra.gem
$ gem build dijkstra.gemspec
$ gem install ./dijkstra-0.1.0.gem
$ ruby app.rb # testing
$ Cost = 6
$ Shortest Path = [1,2,4,3]=> true