Dijkstra algorithm

dijkstra.rb

# dijkstra algorithm
Infinity = 1.0/0

class Graph
  attr_accessor :nodes

  def initialize
    @nodes = {}
  end

  class Node
    attr_accessor :name, :time, :edges, :visited, :prev

    def initialize(name, edges = [])
      @name = name
      @edges = edges
      @visited = false
      @time = Infinity
      @prev = nil
    end

    def print_prev
      node = self
      result = ''
      while(node)
        result << node.name + ' '
        node = node.prev
      end
      result.chop.reverse
    end
  end

  class Edge
    attr_accessor :node, :cost

    def initialize(node, cost)
      @node = node
      @cost = cost
    end
  end

  def add_node(name)
    unless @nodes[name]
      @nodes[name] = Node.new(name)
    end
    @nodes[name]
  end

  def add_edge(source_name, destination_name, weight)
    source_node = add_node(source_name)
    destination_node = add_node(destination_name)
    source_node.edges.push(Edge.new(destination_node, weight))
  end

  def calc_paths_times_from(node_name)
    node = @nodes[node_name]
    node.time = 0
    calc_paths_times(node)
  end

private
  def calc_paths_times(node)
    node.visited = true
    node.edges.each do |edge|
      if edge.node.time > node.time + edge.cost
        edge.node.time = node.time + edge.cost
        edge.node.prev = node
      end
    end
    res = @nodes.min_by {|name, node| node.visited ? Infinity : node.time }
    if res[0] != Infinity && !res[1].visited
      calc_paths_times(res[1])
    end
  end
end

graph = Graph.new

graph.add_edge('a', 'b', 20); graph.add_edge('a', 'g', 90)
graph.add_edge('a', 'd', 80); graph.add_edge('b', 'f', 10)
graph.add_edge('c', 'f', 50); graph.add_edge('c', 'd', 10)
graph.add_edge('c', 'h', 20); graph.add_edge('d', 'g', 20)
graph.add_edge('e', 'b', 50); graph.add_edge('e', 'g', 30)
graph.add_edge('f', 'd', 40); graph.add_edge('f', 'c', 10)
graph.add_edge('g', 'a', 20);

p graph.calc_paths_times_from('c')

graph.nodes.each do |name, node|
  p [name, node.time, node.print_prev]
end