Shortest-Path Routing Algorithms Explained

Dijkstra and A* differ in one line of code and in which nodes they ever look at. Running both by hand on the same six-node graph makes the difference concrete in a way that a description of “informed search” does not.

The graph

Six nodes with coordinates, so a straight-line heuristic exists. Distances are in arbitrary units and edges are undirected.

node   x    y        edges and their cost
  S    0    0        S-A 2.4 , S-B 4.3
  A    2    1        A-B 3.3 , A-C 3.4
  B    1    4        B-D 4.6
  C    5    2        C-D 4.2 , C-G 4.3
  D    5    6        D-G 5.2
  G    9    3        (goal)

Each edge costs a little more than the straight line between its
endpoints, which is what a road does. S-A spans sqrt(4+1) = 2.24
and costs 2.4; C-G spans sqrt(16+1) = 4.12 and costs 4.3.

straight-line distance to G, h(n) = sqrt((9-x)^2 + (3-y)^2):
  h(S) = sqrt(81 + 9)  = 9.49
  h(A) = sqrt(49 + 4)  = 7.28
  h(B) = sqrt(64 + 1)  = 8.06
  h(C) = sqrt(16 + 1)  = 4.12
  h(D) = sqrt(16 + 9)  = 5.00
  h(G) = 0

Because every edge costs at least its straight-line span, this h can never over-estimate: the cheapest route from any node to G is a chain of edges whose costs sum to at least the straight-line distance. That is the condition A* needs, and it is worth checking rather than assuming. From C the true remaining cost is min(4.3, 4.2 + 5.2) = 4.3 against h(C) = 4.12; from B it is min(4.6 + 5.2, 3.3 + 3.4 + 4.3) = 9.8 against h(B) = 8.06.

Edsger Dijkstra published the algorithm in 1959 in “A note on two problems in connexion with graphs” in Numerische Mathematik. A* came from Hart, Nilsson and Raphael in 1968 in “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, and their paper is where the conditions under which A* is optimal are proved.

Dijkstra, settled in order

Dijkstra keeps a priority queue ordered by g(n), the cost from the start. Pop the cheapest unsettled node, settle it, relax its edges. The invariant is that a node is settled with its final distance because every remaining path to it must pass through something already at least as expensive.

pop   settle  g       relaxes
 1     S      0       A = 2.4 ; B = 4.3
 2     A      2.4     B = min(4.3, 2.4+3.3=5.7) -> 4.3 ; C = 5.8
 3     B      4.3     D = 4.3 + 4.6 = 8.9
 4     C      5.8     D = min(8.9, 5.8+4.2=10.0) -> 8.9 ; G = 10.1
 5     D      8.9     G = min(10.1, 8.9+5.2=14.1) -> 10.1
 6     G     10.1     done

settle order: S, A, B, C, D, G     — all six nodes
shortest path: S -> A -> C -> G, cost 10.1

Look at steps 3 and 5. B was settled at 4.3 and D at 8.9, and neither appears in the answer: every route through them is worse. Dijkstra had no way to know that in advance, because it explores outward in every direction at once, in expanding contours of equal cost from the origin. On a road network that means a search from a city centre to the eastern suburbs also settles most of the western suburbs first, because they are nearer the origin than the destination is.

The cost of the algorithm is dominated by the queue rather than by the edges. With a binary heap, each of the V nodes is popped once at log V and each of the E edges can trigger a decrease- key at log V, giving O((V + E) log V). Most heap implementations, including Python’s heapq, have no decrease-key operation, so the usual trick is lazy deletion: push the improved entry as a duplicate and discard any popped entry whose recorded cost is worse than the best known. That keeps the same asymptotic bound and inflates the queue to E entries rather than V, which on a road network — where E is roughly 2.5 times V — is a memory cost worth knowing about before you run one on a continental extract.

A*, on the same graph

A* orders the queue by f(n) = g(n) + h(n), where h estimates the remaining cost. Same graph, same edges, one different sort key:

pop   settle  g      h      f = g+h    relaxes
 1     S      0      9.49   9.49       A: g=2.4, f = 2.4 + 7.28 =  9.68
                                       B: g=4.3, f = 4.3 + 8.06 = 12.36
 2     A      2.4    7.28   9.68       B via A = 5.7, worse, unchanged
                                       C: g=5.8, f = 5.8 + 4.12 =  9.92
 3     C      5.8    4.12   9.92       D: g=10.0, f = 10.0 + 5.00 = 15.00
                                       G: g=10.1, f = 10.1 + 0    = 10.10
 4     G     10.1    0     10.10       goal popped, stop

queue before step 4: G(10.10), B(12.36), D(15.00)
settle order: S, A, C, G           — four of six nodes
shortest path: S -> A -> C -> G, cost 10.1     (same answer)

Same path, same cost, two fewer nodes settled. B and D were never popped at all: their f values sat above the goal’s in the queue, and A* stops the moment the goal comes off the top. The heuristic did not make any individual step cheaper — it changed which steps were taken.

Two of six is a small saving on a toy graph, and it is the wrong thing to take from it. What scales is the shape of the explored region. Dijkstra explores a disc centred on the origin with the destination on its rim; A* with a distance heuristic explores an ellipse with origin and destination at its foci. The area of the disc grows with the square of the route length, the ellipse roughly with the length times how far the heuristic under-estimates, so on a route of hundreds of kilometres across a continental graph the difference is orders of magnitude in nodes touched.

What makes a heuristic safe

Two properties, and they are not the same one.

• Admissible: h(n) never exceeds the true remaining cost. This is what guarantees A* returns an optimal path. Violate it and the failure is silent: a node on the true optimal path gets an inflated f, sinks below the goal in the queue, and the goal is popped with a larger g than it needed. You get a plausible route that is a few percent too expensive, with no error and nothing to compare against.
• Consistent (monotone): h(n) ≤ cost(n, m) + h(m) for every edge. Consistency implies admissibility and additionally guarantees that a settled node never needs reopening, which is what lets the implementation skip the closed-set check.

For road routing by distance, great-circle distance is admissible because roads cannot be shorter than a straight line. For routing by time it is not, until you divide by the maximum speed anywhere in the network: h = haversine(n, goal) / v_max. Use the average speed instead and the heuristic over-estimates on every motorway, and A* quietly returns non-optimal routes — fast, plausible, wrong, and almost impossible to notice without a reference implementation to compare against.

Why real routers do neither

A production router does not run plain A* over a continental graph either. The dominant technique is preprocessing: contraction hierarchies, introduced by Geisberger and colleagues in 2008, order nodes by importance and repeatedly contract the least important one, inserting a shortcut edge wherever removing a node would otherwise lengthen a shortest path. Queries then run bidirectionally, upward only, from both ends. The preprocessing is minutes to hours; the query becomes microseconds.

The catch is that the preprocessing bakes in the cost function. Change the edge weights — traffic, a vehicle-specific restriction, a toll preference — and the shortcuts are no longer valid. That is why real-time traffic in routing engines is handled by customisable contraction hierarchies or by restricting live updates to a small overlay, rather than by rebuilding the hierarchy. It is also why a router that cheerfully accepts arbitrary per-request cost functions is either doing much more work per request than you think, or ignoring part of what you asked for.

Two other things break the clean graph model. Turn restrictions and turn costs are properties of a pair of edges rather than of a node, which requires either an expanded edge-based graph or explicit turn tables. And time-dependent costs — a road that is fast at 03:00 and slow at 08:00 — make the cost of an edge depend on when you arrive at it, so the search must carry a clock. Both are the reason a route computed on a toy graph and a route from a real engine can differ for reasons that have nothing to do with the algorithm. The same one-to-many search underlies isochrones, and repeated shortest-path queries are the input to delivery route optimisation, which is a different and much harder problem.