Dijkstra

Dijkstra's algorithm is a graph-based technique for finding the globally shortest path between a starting node and a target node in a non-negative weighted Directed Acyclic Graph (DAG). It is a DAG in that edges are one way and there are no cycles in the graph; it is weighted in that each traversal of the graph has a certain cost. It is used often in graph-based applications such as social, network routing, and logistics supply modeling. In its simplest form, the algorithm performs in O(v2) where |v| is the number of vertices in the graph.

Details of the algorithm may be found here:

• Wikipedia
• YouTube

Add this line to your application's Gemfile:

gem 'dijkstra'

And then execute:

$ bundle

Or install it yourself as:

$ gem install dijkstra

Use the dijkstra command and pass it a graph file, a starting node, and an ending node.

$ dijkstra my_graph.txt A G
	Shortest path is [A,B,E,G] with total cost 6

A graph file is a txt file containing lines and weights. A line consists of two nodes.

	[A,B,1]
	[B,C,3]
	[C,D,1]
	[D,F,3]
	[E,G,3]
	[F,G,1]
	[A,C,2]
	[B,D,3]
	[B,E,2]
	[D,E,3]

This file must be a Direct Acyclic Graph (DAG):

1. Lines are one way
2. Lines are always weighted
3. There are no cycles

1. Fork it ( http://github.com/jkamenik/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 new Pull Request