Skip to content

Dijkstra's algorithm using a priority queue in Crystal

License

Notifications You must be signed in to change notification settings

geocrystal/dijkstra

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

26 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

dijkstra

Crystal CI License

Dijkstra's algorithm using a priority queue in Crystal.

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.

Installation

  1. Add the dependency to your shard.yml:

    dependencies:
      dijkstra:
        github: geocrystal/dijkstra
  2. Run shards install

Usage

image

require "dijkstra"

gr = Dijkstra::Graph(Char).new(directed: true)

gr.add_edge('a', 'b', 7)
gr.add_edge('a', 'c', 9)
gr.add_edge('a', 'f', 14)
gr.add_edge('b', 'c', 10)
gr.add_edge('b', 'd', 15)
gr.add_edge('c', 'd', 11)
gr.add_edge('c', 'f', 2)
gr.add_edge('d', 'e', 6)
gr.add_edge('e', 'f', 9)

gr.shortest_path('a', 'e')
# => {26, ['a', 'c', 'd', 'e']}

# Directed   : a -> c(9) -> d(20) -> e(26)
# Undirected : a -> c(9) -> f(11) -> e(20)

Contributing

  1. Fork it (https://github.com/geocrystal/dijkstra/fork)
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Add some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create a new Pull Request

Contributors