How A* Improves on Dijkstra (and When It Doesn't)
In my previous post on routing, I used Dijkstra’s algorithm without much discussion of alternatives. The Dijkstra algorithm works for network routing, and for many problems it is the right choice. But pgRouting also ships with pgr_aStar, an implementation of the A* algorithm that can find the same shortest path while exploring fewer edges. The difference comes down to one thing: a heuristic that tells the algorithm which direction to look.
How Dijkstra Explores a Graph
Dutch computer scientist Edsger Dijkstra conceived this algorithm in 1956 while working at the Mathematical Center in Amsterdam. He wanted to demonstrate the capabilities of a new computer called the ARMAC, and he needed a problem that a non-technical audience could understand: given a network of roads connecting cities, what is the shortest route between two of them? According to Dijkstra, he worked out the algorithm in about 20 minutes while sitting at a cafe. He published it in 1959, and it has been a foundation of graph theory and network routing ever since.
The algorithm starts at the source vertex and expands outward in all directions, always visiting the lowest-cost unvisited neighbor next. It has no concept of where the destination is. If you are routing from one corner of a city to the opposite corner, the Dijkstra algorithm will explore vertices in every direction, including those that lead away from the target, before it reaches the destination.
This exhaustive exploration is what makes the Dijkstra algorithm reliable. It guarantees the optimal path as long as all edge costs are non-negative, and it makes no assumptions about the structure of the graph. But it also means the algorithm does more work than strictly necessary for point-to-point routing on a spatial network where you know where the target is located.
How A* Focuses the Search
Twelve years after Dijkstra’s publication, three researchers at the Stanford Research Institute asked a related question: could they make a robot navigate a room full of obstacles? In 1968, Peter Hart, Nils Nilsson, and Bertram Raphael published A* as part of the Shakey the Robot project, which aimed to build one of the first autonomous mobile robots. Nilsson had drafted a routing algorithm for Shakey, Hart proved that with the right modifications it could guarantee optimal paths, and they named it A* simply to distinguish it from the simpler algorithm “A” they had started with. The name stuck.
A* modifies the Dijkstra algorithm by giving the algorithm a sense of direction. At each step, instead of picking the cheapest vertex explored so far, A* also considers how far each candidate vertex is from the destination. It combines the known cost of reaching a vertex with an estimate of the remaining distance, and uses that combined score to decide where to look next.
The estimate is typically straight-line distance on a road network. A vertex that is geographically closer to the destination scores better, so the A* algorithm naturally prioritizes vertices that are heading in the right direction. Vertices in the opposite direction get deprioritized without being explicitly excluded.
The result is the same optimal path that the Dijkstra method would find, but with less wasted exploration. A* still guarantees the shortest route as long as the distance estimate never overstates the true remaining cost, a property that straight-line distance satisfies naturally since the shortest path between two points is always at least as long as the straight line between them.
Using pgr_aStar in pgRouting
The pgr_aStar function in pgRouting requires coordinate columns so it can compute the heuristic. Where pgr_dijkstra only needs id, source, target, cost, and reverse_cost, pgr_aStar also requires x1, y1 (coordinates of the source vertex) and x2, y2 (coordinates of the target vertex) for each edge. If you imported your data with osm2pgrouting as in my previous blog post, the ways table already has these columns.
Let’s route from the Lumina Theater in Southern Village (vertex 30031) to the Carolina Basketball Museum on the UNC campus (vertex 14371) using both algorithms and compare.
First, Dijkstra:
SELECT seq, path_seq, node, edge, cost AS edge_traversal_cost,
agg_cost AS total_route_cost
FROM pgr_dijkstra(
'SELECT id, source, target, cost_s AS cost,
reverse_cost_s AS reverse_cost FROM ways',
30031, -- Lumina Theater
14371, -- Carolina Basketball Museum
directed := false
);
seq | path_seq | node | edge | edge_traversal_cost | total_route_cost
-----+----------+-------+-------+---------------------+--------------------
1 | 1 | 30031 | 37875 | 7.151639637974834 | 0
2 | 2 | 30032 | 35062 | 0.2781187972519185 | 7.151639637974834
3 | 3 | 24406 | 29352 | 0.5361085024738584 | 7.429758435226753
...
61 | 61 | 8064 | 8920 | 1.774480921042361 | 269.00857928253515
62 | 62 | 3188 | 3552 | 7.952249491728545 | 270.7830602035775
63 | 63 | 14371 | -1 | 0 | 278.73530969530606
(63 rows)
Now the same route with A*:
SELECT seq, path_seq, node, edge, cost AS edge_traversal_cost,
agg_cost AS total_route_cost
FROM pgr_aStar(
'SELECT id, source, target, cost_s AS cost,
reverse_cost_s AS reverse_cost,
x1, y1, x2, y2 FROM ways',
30031, -- Lumina Theater
14371, -- Carolina Basketball Museum
directed := false,
heuristic := 5
);
seq | path_seq | node | edge | edge_traversal_cost | total_route_cost
-----+----------+-------+-------+---------------------+--------------------
1 | 1 | 30031 | 37875 | 7.151639637974834 | 0
2 | 2 | 30032 | 35062 | 0.2781187972519185 | 7.151639637974834
3 | 3 | 24406 | 29352 | 0.5361085024738584 | 7.429758435226753
...
61 | 61 | 8064 | 8920 | 1.774480921042361 | 269.00857928253515
62 | 62 | 3188 | 3552 | 7.952249491728545 | 270.7830602035775
63 | 63 | 14371 | -1 | 0 | 278.73530969530606
(63 rows)
The results are identical: same 63 vertices, same edges, same total cost of ~278.7 seconds. Both algorithms found the optimal path.
The difference is in how much work each one did to get there. Running EXPLAIN ANALYZE on both queries repeatedly, Dijkstra ranged from 30ms to 47ms, while A* was consistently 30ms to 31ms.
The variability in the Dijkstra timings is itself revealing: without a heuristic, the number of vertices it visits before reaching the target depends on how it breaks ties among equal-cost candidates, and that fluctuates between runs. A* has less room to wander, so its execution time is more stable.
On a network of this size (roughly 30,000 vertices), the difference is modest. On larger networks with hundreds of thousands of vertices, the gap widens because A* skips progressively more of the graph as the heuristic steers the search north toward the UNC campus instead of expanding in every direction.
When A* Helps
A* provides the most benefit when the source and destination are far apart on the graph and the graph is laid out spatially. In those cases, the heuristic effectively prunes large regions of the graph that Dijkstra would explore. The larger the graph and the longer the route, the more vertices A* skips.
Road networks are a natural fit because they exist in two-dimensional space, and straight-line distance is a reliable lower bound on travel cost.
When A* Makes No Difference
A* and Dijkstra converge in behavior under several conditions.
On short routes where the source and target are close together, Dijkstra does not explore many extra vertices anyway, so the heuristic provides little benefit. The same is true for dense, irregular graphs where many paths have similar costs. The heuristic has less ability to prune when there is no clear geographic shortcut.
A* also requires meaningful coordinates to compute a heuristic. If your graph represents an abstract network like social connections, dependency graphs, or telecommunications links without spatial embedding, there is no geometric heuristic to exploit. Dijkstra is the right choice for these cases.
Finally, if you need shortest paths from one source to many destinations, Dijkstra’s exhaustive expansion is actually an advantage. It computes distances to all reachable vertices in one pass. A* would need a separate search for each destination.
My Recommendation
For point-to-point routing on a spatial network with more than a few thousand vertices, I recommend trying pgr_aStar with the default heuristic and comparing query times against pgr_dijkstra on your data. The path will be identical; the question is whether the heuristic meaningfully reduces search time for your graph size and topology.
For small graphs, one-to-many routing, or non-spatial networks, stick with pgr_dijkstra. It is simpler, requires fewer columns in the edge query, and the performance difference is negligible.
Both algorithms are available in pgRouting.
