Lesson 14 left a line hanging without an explanation:

Connection Scan   0.70 ms   76× faster than the best Dijkstra

No priority queue. No heap. No heuristic.

The full table, our capture:

	our time	against the hand-written heap
Dijkstra, linear scan	876.6 ms	16.4× slower
Dijkstra, hand-written heap	53.4 ms	1.0
Dijkstra, container/heap	73.1 ms	1.37× slower
A*, with the heuristic	77.2 ms	1.45× slower
Connection Scan	0.70 ms	76× faster

Against the naive version — 1252×.

How

Dijkstra asks "which node is cheapest?", and that needs a queue.

CSA does not ask it at all. It keeps a list of connections, sorted by departure time, and walks it once, front to back:

CSA(from, departAt, to):
    arrival[*] ← ∞;  arrival[from] ← departAt
    for each connection c in the list (ascending departure):
        if c.dep < arrival[c.from]: skip     // you cannot be there in time to board
        if c.arr < arrival[c.to]:
            arrival[c.to] ← c.arr
    return arrival[to]

No queue. No revisiting. One pass over an array.

It works because the connections are already sorted by time: reading them in order, you know everything that could have happened earlier by the time each one arrives. The array holds the time ordering, so there is no work left for a queue.

Remember lesson 13's idea — take exactly as much order as the question needs? Here it goes all the way: the order needed is already written into the data, and no structure is required at all.

Lesson 8's question, answered

Lesson 8's homework carried a task nobody had answered:

transit never measured that sort. Estimate it: 196,412 elements, O(n log n). After how many queries does the sort pay for itself? And is the 76× still the right number if you count the preparation?

Measured:

sorting 196412 connections by (departure, trip): 3694130 comparisons, 32.785ms (best of 5)
one query saves 52.7 ms; the sort costs 32.8 ms => it pays for itself after 0.62 queries

It pays for itself after 0.62 queries — that is, before the first one has finished.

And since the sort runs once at server start while queries run in the thousands, the 76× stands. The question was a good one; the answer turned out to be unambiguous.

Lesson 8 presented sorting as an algorithm. Here it is preprocessing — a one-off investment that lets you do without a structure afterwards.

The honest condition

CSA is not a faster Dijkstra. It answers a narrower question.

Dijkstra   arrive 10:27, 147 min,  6 transfers
CSA        arrive 10:27,          11 transfers

The same arrival time. Eleven transfers instead of six.

CSA optimises earliest arrival only. It cannot see the generalised cost — the 2.0 wait weight and the 5-minute transfer penalty — so it does not choose a route by them.

Whether that is acceptable depends on what the program is for. For a passenger who only wants to arrive as early as possible, yes. For one with a suitcase, no.

The speed did not come from a cleverer algorithm. It came from a simpler question. Shrink the question and the structure it needed disappears.

Which is exactly why transit keeps all five algorithms rather than only the fastest. They answer different questions, and only one line in the table tells you which answers are comparable at all.

All three steps

	what it changed	what it bought
linear scan → heap	the structure	~16–19×
heap → A*	knowledge about the problem	−1.45× (it lost)
Dijkstra → CSA	the question, and the data's order	~76×

The middle row matters as much as the other two. It shows the steps are not a ladder: each changes something different, and none guarantees a win.