A* Search Algorithm - Pseudocode

Pseudocode

The following pseudocode describes the algorithm:

function A*(start,goal) closedset := the empty set // The set of nodes already evaluated. openset := {start} // The set of tentative nodes to be evaluated, initially containing the start node came_from := the empty map // The map of navigated nodes. g_score := 0 // Cost from start along best known path. // Estimated total cost from start to goal through y. f_score := g_score + heuristic_cost_estimate(start, goal) while openset is not empty current := the node in openset having the lowest f_score value if current = goal return reconstruct_path(came_from, goal) remove current from openset add current to closedset for each neighbor in neighbor_nodes(current) if neighbor in closedset continue tentative_g_score := g_score + dist_between(current,neighbor) if neighbor not in openset or tentative_g_score <= g_score came_from := current g_score := tentative_g_score f_score := g_score + heuristic_cost_estimate(neighbor, goal) if neighbor not in openset add neighbor to openset return failure function reconstruct_path(came_from, current_node) if came_from in set p := reconstruct_path(came_from, came_from) return (p + current_node) else return current_node

Remark: the above pseudocode assumes that the heuristic function is monotonic (or consistent, see below), which is a frequent case in many practical problems, such as the Shortest Distance Path in road networks. However, if the assumption is not true, nodes in the closed set may be rediscovered and their cost improved. In other words, the closed set can be omitted (yielding a tree search algorithm) if a solution is guaranteed to exist, or if the algorithm is adapted so that new nodes are added to the open set only if they have a lower value than at any previous iteration.