A* ruby implementation to find shortest path and map in a graph with :
- a timeout to stop research when duration > timeout
- a context in a hash for each point in the graph
- the possibility to override default methods
This code has been run and tested on Ruby 1.9 or later
On Debian/Ubuntu/Kubuntu OS :
sudo apt-get install git
gcc is for priority queue.
This package is available in RubyGems and can be installed with:
gem install shortest_path
bundle exec rake spec
More information can be found on the project website on GitHub. There is extensive usage documentation available on the wiki.
Create a basic shortest path finder :
# Create a graph
graph = { :a => { :e => 3, :b => 1, :c => 3},
:b => {:e => 1, :a => 1, :c => 3, :d => 5},
:c => {:a => 3, :b => 3, :d => 1, :s => 3},
:d => {:b => 5, :c => 1, :s => 1},
:e => {:a => 3, :b => 1},
:s => {:c => 3, :d => 1} }
}
# Create a finder
finder = ShortestPath::Finder.new(:a, :e).tap do |shortest_path|
shortest_path.ways_finder = Proc.new { |node| graph[node] }
end
# Change the timeout in seconds
finder.timeout = 2
# Call graph result
finder.path
Overwrite shortest path finder : Find an example in activeroad project
This project is licensed under the MIT license, a copy of which can be found in the LICENSE file.
Users looking for support should file an issue on the GitHub issue tracking page (https://github.com/dryade/shortest_path/issues), or file a pull request (https://github.com/dryade/shortest_path/pulls) if you have a fix available.