Skip to content

Instantly share code, notes, and snippets.

@chischaschos
Created October 29, 2013 22:26
Show Gist options
  • Save chischaschos/7223804 to your computer and use it in GitHub Desktop.
Save chischaschos/7223804 to your computer and use it in GitHub Desktop.
dijkstra shortest path in ruby
require 'spec_helper'
SP = ->(graph, from_node, to_node, nodes = Hash.new(0), visited = [], i = 0) {
return nodes[from_node] if from_node == to_node
neighbours = graph[from_node].reject {|k, v| visited.include?(k) }
neighbours.each do |k, v|
if nodes[k] == 0 || nodes[from_node] + v < nodes[k]
nodes[k] = nodes[from_node] + v
end
end
smallest_node = neighbours.sort_by {|k, v| nodes[k]}.first.first
visited << from_node
raise 'Loooppppiiing' if i > 7
SP.(graph, smallest_node, to_node, nodes, visited, i + 1)
}
describe SP do
let(:graph) do
{
'1' => {
'2' => 7,
'3' => 9,
'6' => 14
},
'2' => {
'1' => 7,
'3' => 10,
'4' => 15
},
'3' => {
'1' => 9,
'2' => 10,
'6' => 2,
'4' => 11
},
'4' => {
'2' => 15,
'3' => 11,
'5' => 6,
},
'5' => {
'4' => 4,
'6' => 9,
},
'6' => {
'1' => 14,
'3' => 2,
'5' => 9,
}
}
end
it '1 to 1' do
expect(SP.(graph, '1', '1')).to eq 0
end
it '1 to 2' do
expect(SP.(graph, '1', '2')).to eq 7
end
it '1 to 6' do
expect(SP.(graph, '1', '6')).to eq 11
end
it '1 to 5' do
expect(SP.(graph, '1', '5')).to eq 20
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment