A* is a pathfinding algorithm that uses heuristics to guide its search. It can be considered as a generalization of Dijkstra’s algorithm. A* only finds a path between two given nodes, where as Dijkstra’s algorithm finds the shortest path tree from a start node.

Variables and Functions^[1]

A* formulates the problem space using a weighted directed graph and uses the following variables and functions:

• c_{ij}: cost of the arc going out from node i to node j.
• g(n): the cost of the path from start node s to n with minimum cost so far found by A*.
• h(n): heuristic function that estimates the cost of the cheapest path from n to the goal node. If the heuristic function is admissible, A* is guaranteed to find an optimal path. If h(n) is also consistent, nodes never need to be reopened once closed.
• f(n): evaluation function or f-value. Defined as follows: f(n) = g(n) + h(n)
• OpenSet: a min-priority queue containing all currently open nodes, ordered by their f-values.
• \Gamma(n_i): successor operator. Yields all the successors n_j of n_i and the arc costs c_{ij}.

Algorithm

Following pseudocode is adapted from the original article ^[1:1]:

1. First mark s as open, calculate the f(s) and add it to the priority queue.
2. Select the open node n whose f-value is smallest from the queue. Resolve ties arbitrarily, but always in favor of any goal node.
3. If n is a goal node, mark n as closed and terminate the algorithm.
4. Otherwise, mark n as closed and apply the successor operator \Gamma to n. Calculate f-values for each successor of n and mark as open each successor not already marked closed. Go to Step 2.

References