Dijkstra's algorithm rests on one claim.

Why it is correct

When you take the cheapest unprocessed node next, its distance is already final.

The proof fits in a sentence. Suppose there were a cheaper route to node v that we have not found. That route must cross the boundary between processed and unprocessed nodes — and its first unprocessed node u is cheaper than v. So u would have been taken before v, not after.

Which is impossible, provided no edge is negative. Because then "further along the route" means "not cheaper". Step 4 shows what happens when that condition is broken.

Compare with lesson 14: BFS's layers were the same argument in a simpler form. Dijkstra is BFS with cost in place of layers.

The algorithm

Dijkstra(from, to):
    dist[*] ← ∞;  dist[from] ← 0
    frontier ← {from at 0}

    while frontier is not empty:
        v, d ← the CHEAPEST element of frontier      // ← the whole point
        if done[v]: skip                             // a stale entry
        done[v] ← true
        if v = to: return the path and d
        for each edge (v → w, cost c):
            if d + c < dist[w]:
                dist[w] ← d + c
                prev[w] ← v
                put w into frontier at d + c

Compare it with lesson 14's BFS. Three things differ: a dist array instead of seen, the condition d + c < dist[w] instead of !seen[w], and the frontier hands back the cheapest rather than the oldest.

The third is the only one that needs a structure.

Two frontiers

A heap (lesson 13): Push and Pop cost O(log V).

A linear scan: no structure at all; at every step look at all V nodes and take the smallest. O(V).

Both are correct and return the same path. Step 5 measures what the difference costs.

Stale entries: why the heap holds more than there are nodes

When a cheaper route to w turns up, w may already be in the heap with an older, dearer value. What then?

There are two answers.

Decrease-key: find w in the heap and correct its value. But the heap does not know where w is — that needs a separate index, kept in step with every swap. In lesson 13 you measured 6,922 swaps for a single 10,000-element build; every one of them would get more expensive.

Lazy deletion: just push w again. The heap then holds several entries for one node; the first one popped is the cheapest, and the rest are recognised by done[v] and skipped.

The second is what transit writes and what you will write. The price: the heap holds a little more than it has nodes. How much more, you measure in step 4.

The cost

V pops at O(log V), E pushes at O(log V):

O((V + E) log V) with a heap. O(V² + E) with a linear scan.

On a sparse graph — and your mean degree is 1.49 — the first is nearly linear and the second is quadratic.