Dijkstra expands equally in every direction. Looking for a route from Šeškinė to Naujininkai it explores Fabijoniškės with just as much diligence — because it does not know where the destination is.

A* adds one thing: an estimate of what is left. Instead of d, nodes are ordered by d + h(v), where h(v) guesses the remaining cost.

If h never overestimates the remaining cost the answer stays correct — such an h is called admissible. And then the search leans towards the goal, and sideways branches drop out earlier.

It sounds like a free improvement. transit built it.

It is correct

TestAStarMatchesDijkstra   A* matches Dijkstra's optimum on all 120 queries

All 120 queries, the same optimal answer. The implementation is sound, the heuristic is admissible, the algorithm does what the textbook says.

And it loses

                                          our capture   against the hand-written heap
Dijkstra, hand-written heap                   53.4 ms   1.0
A*, container/heap + heuristic                77.2 ms   1.45x slower

BenchmarkRouter gives 1.75×. transit's README states 1.05–1.09× slower; on our machine the defeat is larger, not smaller.

We built it, and it lost.

Why — and this is the important part of the step

A* prunes in proportion to what its heuristic can see. So how much does it see?

TestHeuristicTightness   over 187 queries — h(origin) as a fraction of true optimal cost:
                           mean 4.1%, min 0.5%, max 22.1%

4.1%. The heuristic sees a twenty-fifth of the cost it is supposed to bound. At worst, 0.5%.

The reason was measured separately:

TestHeuristicBlindToWaiting   over 186 journeys: mean elapsed time 99.7 min,
                              mean generalised cost 145.0 equivalent-min,
                              mean transfers 3.57
                              generalised cost exceeds elapsed time by 45%

The heuristic is geometric: distance to the destination divided by the fastest observed speed. Geometry can model riding. It cannot model waiting for the next departure or the penalty for changing vehicle — and those are 45% of the cost.

The cost of a transit journey depends less on WHERE you are than on WHEN. The heuristic can only see "where".

And the result shows in the node counts:

TestAStarSpread
  short_hop            dijkstra settled  1974 | A* settled  1760 | reduction 10.8%
  cross_city           dijkstra settled 15154 | A* settled 12829 | reduction 15.3%
  late_night           dijkstra settled  9923 | A* settled  9923 | reduction  0.0%
  exhaustive_no_route  dijkstra settled   147 | A* settled   147 | reduction  0.0%

On two queries out of four, exactly zero. And where it does prune 10–15%, the work saved does not cover what computing the heuristic costs at every node.

The cost weights are not invented

Worth pausing here: perhaps A* loses because the cost model was made artificially complicated — tangled up precisely so that geometry would look helpless?

No. The weights come from the transport planning literature:

• wait weight 2.0 — Wardman's reviews put the ratio of waiting to in-vehicle time at 2:1; the Metropolitan Transportation Commission (Travel Model One) and the San Francisco County TA (CHAMP 5.0) both use exactly 2.0;
• transfer penalty 5 min — the literature says 5–15; MTC charges 5/10/30 minutes for the first, second and third transfer, SFCTA a flat 6. The low end was taken.

And the model was measured against pure time:

TestGeneralisedCostPrefersFewerTransfers
  over 200 queries: 10 chose a later arrival, 149 used fewer transfers

149 routes out of 200 got fewer transfers, and only 10 arrived later. That is a correction to the model, not a trick to make the queue look necessary.

And yet A* wins on roads

It is easy to draw the wrong conclusion here: "A* does not work". Wrong.

In car routing, A* and its successors — contraction hierarchies — are the standard. There the heuristic works beautifully, because the cost of a car journey really is close to distance: no timetable, no waiting, and speeds that vary within narrow limits.

Transit routing went the other way — to CSA and RAPTOR, which have no heuristic at all.

The same shortest-path problem. Opposite winners.

Bast et al. ("Route Planning in Transportation Networks", MSR-TR-2014-4) treat this split as fundamental; Geisberger, who introduced contraction hierarchies, documents that the method "completely fails for timetable networks".

An algorithm is chosen not by the problem but by the problem's STRUCTURE.

Why A* is not in your library

Try writing h(v) for your network: how many days remain from book v to the destination?

You cannot. Books have no coordinates. There is nothing to measure without doing the search itself, and an estimate you can only compute by searching is not an estimate.

A* needs knowledge about the problem that your graph does not have. Which is why you are not building it in this lesson — not because it is hard, but because there is nothing for it to stand on.

That is an answer too, and an honest one.