Dijkstra’s algorithm in ruby

dijkstra.rb

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]