Predictive Analysis with Graph Theory - Graph Databases - page 173

Figure 7-11. Finally reaching Perth, a mere 50 driving hours from Sydney
The A* Algorithm
The A* (pronounced “A-star”) algorithm improves on the classic Dijkstra algorithm. It
is based on the observation that some searches are informed , and that by being informed
we can make better choices over which paths to take through the graph. In our example,
an informed search wouldn't go from Sydney to Perth by traversing an entire continent
to Darwin first. A* is both like Dijkstra in that it can potentially search a large swathe
of a graph, but it's also like a greedy best-first search insofar as it uses a heuristic to guide
it. A* combines aspects of Dijkstra's algorithm, which prefers nodes close to the current
starting point, and best-first search, which prefers nodes closer to the destination, to
provide a provably optimal solution for finding shortest paths in a graph.
In A* we split the path cost into two parts: g(n) , which is the cost of the path from the
starting point to some node n ; and h(n) , which represents the estimated cost of the path
from the node n to the destination node, as computed by a heuristic (an intelligent
guess). The A* algorithm balances g(n) and h(n) as it iterates the graph, thereby ensuring
that at each iteration it chooses the node with the lowest overall cost f(n) = g(n) + h(n) .
As we've seen, breadth-first algorithms are particularly good for path finding. But they
have other uses as well. Using breadth-first search as our method for iterating over all
elements of a graph, we can now consider a number of interesting higher-order