def _a_star_search_internal(graph, start, goal):
frontier = PriorityQueue()<EOL>frontier.put(start, <NUM_LIT:0>)<EOL>came_from = {start: None}<EOL>cost_so_far = {start: <NUM_LIT:0>}<EOL>goal_reached = False<EOL>while not frontier.empty():<EOL><INDENT>current = frontier.get()<EOL>if current == goal:<EOL><INDENT>goal_reached = True<EOL>break<EOL><DEDENT>for next_node in graph.neighbors(current):<EOL><INDENT>new_cost = cost_so_far[current] + graph.edge_cost(current, next_node)<EOL>if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:<EOL><INDENT>cost_so_far[next_node] = new_cost<EOL>priority = new_cost + heuristic(goal, next_node)<EOL>frontier.put(next_node, priority)<EOL>came_from[next_node] = current<EOL><DEDENT><DEDENT><DEDENT>return came_from, cost_so_far, goal_reached<EOL>
Performs an A* search, returning information about whether the goal node was reached
    and path cost information that can be used to reconstruct the path.