bellman

bellman.rb

VERTICIES = ["S","A", "B", "C", "D", "E"]
complete = false

MEMO = {
  S: 0,
  A: Float::INFINITY,
  B: Float::INFINITY,
  C: Float::INFINITY,
  D: Float::INFINITY,
  E: Float::INFINITY
}

GRAPH = [
  {from: "S", to: "A", cost: 4},
  {from: "S", to:"E", cost: 6},
  {from: "A", to:"C", cost: 6},
  {from: "B", to:"A", cost: 3},
  {from: "C", to:"B", cost: 2},
  {from: "D", to:"C", cost: 3},
  {from: "D", to:"A", cost: 10},
  {from: "E", to: "D", cost: 8}
]

#iterate over verticies
#use current vertex from our verticies array  to select outgoing edges from GRAPH array

def iterate
  do_over = false

  VERTICIES.each do |from_vertex|
    edges = GRAPH.select { |path|
      path[:from] == from_vertex
    }

    edges.each do |edge|
      from = edge[:from].to_sym
      to = edge[:to].to_sym
      potential_cost = MEMO[from] + edge[:cost]

      if potential_cost < MEMO[to]
        MEMO[to] = potential_cost
        do_over = true #this can only happen once to warrant a do_over
      end
    end
  end
  do_over
end

until(complete == true)
  complete = true if iterate == true
end

puts MEMO