Dijkstra: Always Expand the Cheapest Frontier

"Dijkstra is just BFS that grew up and learned to count money. Instead of a plain queue, it uses a priority queue — always expanding the cheapest-known node next. That one upgrade turns 'fewest hops' into 'lowest cost.'"

The Algorithm

Dijkstra finds the cheapest path from one source to every other node in a graph with non-negative weights. The machinery:

Keep a tentative distance to every node, starting at 0 for the source and infinity for the rest.
Put (0, source) in a min-heap (priority queue).
Pop the node with the smallest tentative distance. Finalize it — its distance is now certain.
Relax its neighbors: for each, if going through the just-finalized node is cheaper than its current tentative distance, update it and push the new distance to the heap.
Repeat until the heap is empty.

Compare to BFS: same expand-the-frontier shape, but the frontier is a priority queue keyed by total cost instead of a plain FIFO queue. Dijkstra is, almost literally, BFS with a heap — the Heaps track and the Graphs track meeting in one algorithm.

Why Finalizing on Pop Is Safe

Here's the greedy insight that makes Dijkstra correct: when you pop the closest unfinalized node, its tentative distance is already its true shortest distance. Why? Every other path to it would have to go through some node that's still in the heap — and those are all farther than the one you just popped, and since weights are non-negative, detouring through a farther node can only add cost. So no cheaper path can ever appear. That's the whole proof, and it's also exactly why Dijkstra requires non-negative weights: a negative edge would let a 'farther' node secretly offer a cheaper route, breaking the guarantee — which is the cliffhanger for the next lesson.

Dijkstra = BFS with a min-heap: repeatedly pop the cheapest-known node, finalize it, and relax its neighbors. Finalize-on-pop is safe because non-negative weights mean no farther node can offer a cheaper detour. O((V+E) log V) with a heap.

Where It Runs the World

Dijkstra (and its heuristic-guided cousin A*) is the shortest-path algorithm in your GPS, in network routing protocols (OSPF computes least-cost routes between routers with it), in game pathfinding, in flight/transit planners. Any 'cheapest route through a weighted network with non-negative costs' is a Dijkstra. The priority queue you learned in the Heaps track is what makes it efficient — without a heap, repeatedly finding the cheapest frontier node would be O(V²) instead of O((V+E) log V).

Pippa's Confession

Dijkstra intimidated me as 'the hard graph algorithm' until Dad said five words: "It's BFS with a heap." Suddenly it wasn't new — it was two things I already knew, snapped together. The queue becomes a priority queue; 'distance in hops' becomes 'distance in cost.' Everything else is the same frontier-expansion I'd done a dozen times. The scariest algorithms are often just two familiar pieces I hadn't yet seen click into each other.

Code

Dijkstra with a priority queue·python

import heapq

def dijkstra(graph, source):
    """Cheapest distance from source to every node. Non-negative weights only.
    graph: {node: [(neighbor, weight), ...]}.  O((V+E) log V)."""
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    heap = [(0, source)]                  # (tentative_distance, node)
    while heap:
        d, u = heapq.heappop(heap)        # the cheapest-known frontier node
        if d > dist[u]:
            continue                       # stale entry, skip
        for v, w in graph[u]:
            nd = d + w                     # cost to reach v through u
            if nd < dist[v]:               # RELAX: found a cheaper route to v
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

graph = {
    "A": [("B", 1), ("C", 4)],
    "B": [("C", 2), ("D", 5)],
    "C": [("D", 1)],
    "D": [],
}
print(dijkstra(graph, "A"))   # {'A':0, 'B':1, 'C':3, 'D':4}
# A->C directly is 4, but A->B->C is 1+2 = 3 (cheaper). A->B->C->D = 4.
# The heap always hands back the closest unfinalized node next.

Exercise

On the graph A→B (1), A→C (4), B→C (2), C→D (1), B→D (7), run Dijkstra from A by hand: what's the final shortest distance to each node, and which node does the heap finalize first, second, third? Then explain in one sentence why, the moment C is popped from the heap, you can be certain no cheaper path to C will ever be found.

Hint

Distances: A:0, B:1, C:3 (via B), D:4 (via C). Finalize order by smallest distance: A(0), B(1), C(3), D(4). When C is popped at distance 3, every other route to C must pass through a node still in the heap that's already ≥3 away, and non-negative edges can't reduce that — so 3 is final.

The Algorithm

Why Finalizing on Pop Is Safe

Where It Runs the World

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0