A*

The A* algorithm is a popular Best First Search algorithm for finding the shortest path between two known nodes.

Info

The A* algorithm uses two pieces of information in order to make an estimate about how optimal a given node is:

• $g(x)$ → The cost from the start node to node $x$.
• $h(x)$ → The heuristic function describing the estimated cost to the goal node.

This produces $f(x)=g(x)+h(x)$ which A* attempts to find the minimal value of.

Process

The A* algorithm follows the following process:

1. Add the neighbours of the starting node to the open set/frontier.
2. Select the member of the open set/frontier with the lowest $f(x)$ value, and expand it’s neighbours, adding them to the open set/frontier.
3. Continue until the goal node is reached.

---

Complexity

The complexity values for A* are:

Aspect	Complexity
Time	$O(E)$
Space	$O(V)$

---

Example

Run the A* algorithm on the following graph:

Note

The result of $h(x)$, the heuristic function, is marked in gold below each node. Edge weights are in black next to each edge.

---

Here, the open set/frontier was:

Node	$h(x)$	$g(x)$	$f(x)=g(x)+h(x)$
$b$	$12$	$4$	$16$
$c$	$11$	$3$	$14$

---

Here, the open set/frontier was:

Node	$h(x)$	$g(x)$	$f(x)=g(x)+h(x)$
$b$	$12$	$4$	$16$
$d$	$6$	$10$	$16$
$e$	$4$	$13$	$17$

---

Here, the open set/frontier was:

Node	$h(x)$	$g(x)$	$f(x)=g(x)+h(x)$
$d$	$6$	$10$	$16$
$e$	$4$	$13$	$17$
$f$	$11$	$9$	$18$

---

Here, the open set/frontier was:

Node	$h(x)$	$g(x)$	$f(x)=g(x)+h(x)$
$e$	$4$	$12$	$16$
$f$	$11$	$9$	$18$

---

Here, the open set/frontier was:

Node	$h(x)$	$g(x)$	$f(x)=g(x)+h(x)$
$z$	goal node	$17$	$17$
$f$	$11$	$9$	$18$

Since the goal node is a member of the open set/frontier we just select it, and our shortest path is the one from $acdez$