Shortest Path

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.