dijkstra's_algorithm

dijkstra.rb

graph = {}
graph['start'] = Hash.new
graph['start']['a'] = 6
graph['start']['b'] = 2

graph['a'] = Hash.new
graph['a']['fin'] = 1
graph['b'] = Hash.new
graph['b']['a'] = 3
graph['b']['fin'] = 5
graph['fin'] = Hash.new

inf = Float::INFINITY
costs = {}
costs['a'] = 6
costs['b'] = 2
costs['fin'] = inf

parents = {}
parents['a'] = "start"
parents['b'] = "start"
parents['fin'] = nil

processed = [0] # <-cause in function


def find_lowest_cost_node hashes, arr
  lowest_cost = Float::INFINITY
  lowest_cost_node = nil
  for node in hashes
    cost = node[1]
    if (cost < lowest_cost) && !(arr.include? node[0]) # include? for nil class
      lowest_cost = cost
      lowest_cost_node = node[0]
    end
  end
  lowest_cost_node
end



node = find_lowest_cost_node costs, processed
until node.nil?
  cost = costs[node]
  neighbors = graph[node]
  neighbors.each_pair do |key, value|
    new_cost = cost + value
    if costs[key] > new_cost
      costs[key] = new_cost
      parents[key] = node
    end
  end
  processed << node
  node = find_lowest_cost_node costs, processed
end


puts costs['fin']