07_dijkstra.rb

# Dijjkstra's Algorithm
# Book: Grokking Algorithms by Aditya Y. Bhargava
# Chapter: 7

class ShortestPath
  def initialize(start_node, dest_node, graph)
    @start_node = start_node
    @dest_node = dest_node
    @graph = graph

    @costs = {}.tap do |costs|
      @graph[@start_node].each do |node, cost|
        costs[node] ||= cost
      end
      @graph.each do |node, _|
        next if node == @start_node
        costs[node] ||= Float::INFINITY
      end
    end

    @parents = {}.tap do |parents|
      @graph[@start_node].each do |node, _|
        parents[node] = @start_node
      end
      @graph.each do |node, _|
        next if node == @start_node
        parents[node] ||= nil
      end
    end

    @processed = []

    find_shortest_path
  end

  def find_lowest_cost_node
    lowest_cost = Float::INFINITY
    lowest_cost_node = nil
    @costs.keys.each do |node|
      cost = @costs[node]
      if cost < lowest_cost && !@processed.include?(node)
        lowest_cost = cost
        lowest_cost_node = node
      end
    end
    lowest_cost_node
  end

  def find_shortest_path
    while (node = find_lowest_cost_node)
      cost = @costs[node]
      neighbors = @graph[node]
      neighbors.keys.each do |n|
        new_cost = cost + neighbors[n]
        if @costs[n] > new_cost
          @costs[n] = new_cost
          @parents[n] = node
        end
      end
      @processed << node
    end
  end

  def to_s
    n = @dest_node
    path = [@dest_node]
    while n != @start_node
      n = @parents[n]
      path.unshift(n)
    end
    path.join(' => ') + " (cost: #{@costs[@dest_node]})"
  end
end

# Example Graph
graph = {
  'start' => {
    'a' => 6,
    'b' => 2,
  },
  'a' => {
    'fin' => 1,
  },
  'b' => {
    'a' => 3,
    'fin' => 5,
  },
  'fin' => {},
}
puts ShortestPath.new('start', 'fin', graph) # => start => b => a => fin (cost: 6)

# Excercise A
graph = {
  'start' => {
    'a' => 5,
    'b' => 2,
  },
  'a' => {
    'c' => 4,
    'd' => 2,
  },
  'b' => {
    'a' => 8,
    'd' => 7,
  },
  'c' => {
    'fin' => 3,
    'd' => 6,
  },
  'd' => {
    'fin' => 1,
  },
  'fin' => {},
}
puts ShortestPath.new('start', 'fin', graph) # => start => a => d => fin (cost: 8)

# Exercise B
graph = {
  'start' => {
    'a' => 10,
  },
  'a' => {
    'c' => 20,
  },
  'b' => {
    'a' => 1,
  },
  'c' => {
    'b' => 1,
    'fin' => 30,
  },
  'fin' => {},
}
puts ShortestPath.new('start', 'fin', graph) # => start => a => c => fin (cost: 60)