Lesson 14 ended like this:

BFS answers "in how many hops", because every hop costs the same. In the time-expanded graph they do not — and BFS ignores that.

Now the edges of your library network have a cost too: days between borrows. A reader picked up one book after three days and the next after five weeks.

The question has changed. Not "how many books", but "how many days".

$ algo route
nodes 1000, edges 742, weights = days between borrows (1..60)
route from 0 to 194

                                 hops       days
  BFS (fewest hops)                12        402
  Dijkstra (fewest days)           12        191

  the cheapest route takes 0 more hops and saves 211 days

The same hop count. An answer twice as good.

Both routes are 12 edges long, so BFS cannot tell them apart — to it they are identical. But one takes 402 days and the other 191.

And this is not an edge case. Of 561 reachable books, the route BFS picks differs from the cheapest one 197 times (35.1%).

What that needs

Dijkstra's algorithm asks, at every step: which unprocessed node is cheapest?

You know that question. In lesson 13 you built the structure that answers it in O(log n) and whose minimum is a[0].

No new structure is built in this lesson. What is built is the search that structure existed for all along.

Guess before you read on

The heap is optional. Instead of it you can scan every node at each step and take the smallest — O(V) instead of O(log V). The answer will be the same; only the speed differs.

In lesson 1 the instrument chosen was an operation counter, not a clock — because a counter does not depend on the machine.

How many times more work will the linear version do? And how many times longer will it take? Will those two numbers match?

Write both down. Step 5 measures them, and they will not match — and why is the sixth time that has happened in this course.