Skip to content

Instantly share code, notes, and snippets.

@johand
Created April 13, 2019 17:39
Show Gist options
  • Save johand/e40497f5cfca4ea85d825902a00e3373 to your computer and use it in GitHub Desktop.
Save johand/e40497f5cfca4ea85d825902a00e3373 to your computer and use it in GitHub Desktop.
Dijkstra’s algorithm in ruby
class Dijkstra
attr_reader :graph, :costs, :parents, :processed
def initialize(graph, costs, parents)
@graph = graph
@costs = costs
@parents = parents
@processed = []
end
def nodes
node = lowest_cost_node
while node
cost = costs[node]
neighbors = graph[node]
neighbors.keys.each do |n|
new_cost = cost + neighbors[n]
if costs[n].nil? || costs[n] > new_cost
costs[n] = new_cost
parents[n] = node
end
end
processed << node
node = lowest_cost_node
end
end
def shortest_path
parent = parents[:finish]
path = [:finish]
while parent
path.unshift(parent)
parent = parents[parent]
end
path
end
private
def lowest_cost_node
lowest_cost = Float::INFINITY
lowest_cost_node = nil
costs.each do |node, cost|
unless processed.member?(node)
if cost < lowest_cost
lowest_cost = cost
lowest_cost_node = node
end
end
end
lowest_cost_node
end
end
graph = {
start: { a: 5, b: 2 },
a: { c: 4, d: 2 },
b: { a: 8, d: 7 },
c: { d: 6, finish: 3 },
d: { finish: 1 },
finish: {}
}
costs = {
a: graph[:start][:a],
b: graph[:start][:b],
finish: Float::INFINITY
}
parents = {
a: :start,
b: :start,
finish: nil
}
d = Dijkstra.new(graph, costs, parents)
d.nodes
puts "Distance: #{costs[:finish]}, Path: #{d.shortest_path}"
# => Distance: 8, Path: [:start, :a, :d, :finish]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment