# A* Algorithm

Both the Breadth First Search and Dijkstra's Algorithm produce a spanning tree for the graph to which they are applied by continually considering a set of nodes that might be added to an existing (initially degenerate) tree. Let us call this set of nodes that are considered at each step through the algorithm the "frontier".

Notice that in both algorithms, the frontier expands in all directions away from the tree built so far. This is reasonable if you're trying to find a path to all locations or to many locations. However, a common case is to find a path to only one location. As such, it will be advantageous to make the frontier expand towards this goal location more than it expands in other directions.

To accomplish this, let us define a heuristic function that tells us how close we are to the goal. In the case of edge-weighted graphs where the nodes represent physical locations, and the edge weights represent the lengths of paths that can be taken to get from one starting location $(x_1, y_1)$ to another $(x_2,y_2)$, the heuristic used might be as simple as the Euclidean distance between the two nodes.

$$h(n) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$

In general, you can think of the heuristic function as an estimate of the cost of the cheapest path from the starting node to the "goal" node.

To minimize time spent exploring directions that aren't promising while still doing well in finding the shortest path, the A* algorithm makes a slight modification to Dijkstra's algorithm. The priority attached to a particular node is no longer the distance/cost required to get back to the starting node from the current node, as discovered so far -- but rather, it is the sum of this cost and the output of the heuristic function as applied to the starting and current nodes. (In this way, the priority given is the cost to get from the start to some node n plus the estimated cost to get from n to the goal node.)

To change Dijkstra's algorithm into the A* algorithm, one simply adds some appropriate heuristic() function and alters what happens when an edge is "relaxed", as can be seen in the code below:

Dijkstra's version of Relaxing an Edge: (see the rest...)

public void relax(DirectedEdge e) {
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;

// now update priority queue...
if (pq.contains(w))
// overwrite distance associated with w to distTo[w]
pq.decreaseKey(w, distTo[w]);
else
// add vertex w, setting its distance to distTo[w]
pq.insert(w, distTo[w]);
}
}

The A* Version of Relaxing an Edge:

public void relax(DirectedEdge e) {
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;

// now update priority queue...
if (pq.contains(w))
// overwrite distance associated with w to distTo[w]
pq.decreaseKey(w, distTo[w]+heuristic(source,w));
else {
// add vertex w, setting its distance to distTo[w]
pq.insert(w, distTo[w]+heuristic(source,w));
}
}
}

One can show that A* will find a shortest path if the heuristic used (which can vary) never overestimates the cost to reach the destination node (which we abbreviate by saying the heuristic is admissible) and if the search space is a tree.

Supposing that $h(n)$ is the heuristic function and $c(n,m)$ gives the cost of traveling from node $n$ to node $m$ -- one way to guarantee that a heuristic is admissible is to ensure that if for every node $n$ and for every adjacent successor node $n'$ of $n$, we have $h(n) \le c(n,n') + h(n')$. Heuristic functions with this property are called consistent. One should note that, as said before, whenever $h$ is consistent $h$ will definitely also be admissible, but the reverse need not be the case (although frequently they do go hand-in-hand).