The algorithm was invented in 1968 by Nils Nilsson, Bertram Raphael, and Peter E. Hart during their work on improving path planning of Shakey the robot - a general purpose robot developed at the Artificial Intelligence Center of the Stanford Research Institute.

A* is similar to the Dijkstra algorithm in that it searches among all the possible paths. The improvement is that it uses heuristics to first consider the paths that seem to lead to the target quicker.

The basic usage is as follows:

select * from pgr_aStar('select gid as id, source, target, cost, x1, y1, x2, y2 from pgr.ways', 79240, 9064); 

This time, we need to provide a bit more data to the algorithm; not only the edge ID, source vertex, target vertex, and cost, but also coordinates of the source and target vertices needed for the heuristic magic to happen.

The output is exactly what we saw when using one-to-one Dijkstra:

  seq|  path_seq|   node|   edge|             cost|         agg_cost
-----+----------+-------+-------+-----------------+-----------------
    1|         1|  79240|  69362| 169.494690094003|                0
    2|         2|  52082|  44175| 107.754808368861| 169.494690094003
...

And the found route is also exactly the same:

We searched for the shortest path between the same vertices, so we can draw some assumptions by now. Basically, A* is quicker than Dijsktra, but the difference depends on the data and the dataset size. On my box, calculating Dijsktra for our test points takes roughly 470 ms, while A* takes 450 ms.

This is by no means a trustworthy benchmark of course, but it gives a general impression of what to expect.

It is also worth remembering that, since A* star is a best-fit algorithm, it tries to predict what vertices to evaluate in order to find the shortest path; it may not return the most optimal result. At the same time, Dijkstra evaluates more data and guarantees the results to be optimal.