## start can be an array or an item
#  there can be only one goal
def a_star_search(graph, start, goal)
    case start
    when Array
    else
        start = [start]
    end
    
    ## 
    came_from   = {}
    cost_so_far = {}

    frontier = PriorityQueue.new

    start.each { |s| frontier.put(s, 0) 
                    came_from[ s]   = nil
                    cost_so_far[ s] = 0
                }

    while !frontier.empty?
        current = frontier.next
        break if current == goal
            
        graph.neighbors(current).each do |n|
            new_cost = cost_so_far[ current] + graph.cost(current, n)
            if !cost_so_far.key?( n) || new_cost < cost_so_far[ n]
                priority = new_cost + heuristic( goal, n)
                frontier.put( n, priority)
                cost_so_far[ n] = new_cost
                came_from[ n]   = current
            end
        end
    end

    return came_from, cost_so_far[ goal]
end