Breadth-first search finds shortest paths by counting edges, and the moment edges carry weights, counting stops working: a three-edge back road can beat a one-edge toll bridge. Dijkstra's algorithm repairs the guarantee with one substitution, a priority queue in place of the plain queue, so the search always extends the cheapest path discovered so far, which makes the first arrival at every node provably the best one. It's the idea behind every GPS route and most network routing, and it runs in O((V + E) log V).

The entire contract rests on one assumption: no edge weight is negative. Honor it and the greedy choice is bulletproof. Break it and the algorithm confidently returns wrong numbers, which is why the assumption gets its own section below.

Watch it work. Five nodes, directed weighted edges: A→B costs 4, A→C costs 1, C→B costs 2, C→D costs 5, B→E costs 1, and D→E costs 3. From A, the first pop relaxes both edges: B tentatively 4, C tentatively 1. Predict before reading on: does B end up costing 4?

No, and the reason is the whole algorithm. The heap pops C first because 1 < 4, and relaxing C→B finds 1 + 2 = 3, beating the direct 4 before B was ever finalized. The walk continues cheapest-first: B at 3, E at 4 (through B), D at 6. Why is a popped node final? Any other route to it would have to pass through some node still waiting in the heap, and everything in the heap already costs at least as much. With no negative edges to refund the difference, no detour can catch up.

import heapq

def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, int]:
    # graph[node] holds (neighbor, weight) pairs
    distance = {start: 0}
    heap = [(0, start)]

    while heap:
        dist, node = heapq.heappop(heap)

        # Stale entry: this node already finalized cheaper
        if dist > distance.get(node, float("inf")):
            continue

        for neighbor, weight in graph.get(node, []):
            candidate = dist + weight

            # Relax: keep the cheaper arrival
            if candidate < distance.get(neighbor, float("inf")):
                distance[neighbor] = candidate
                heapq.heappush(heap, (candidate, neighbor))

    return distance

The implementation above uses lazy deletion. When a node's distance improves, the old heap entry stays put and a new pair gets pushed, so the same node can sit in the heap several times. The dist > distance[node] check at the top recognizes the leftovers and skips them, which doubles as the visited check: no separate set required.

You might think a careful implementation could tolerate a negative edge or two. The failure is in the logic, not the code. Take three nodes: A→B costs 2, A→C costs 3, and C→B costs -2. Dijkstra pops B at distance 2 and declares it final. Only afterward does C get processed, revealing the route A→C→B at cost 3 - 2 = 1. Too late: finalized means finalized, and the algorithm reports 2 for a node whose true distance is 1.

The proof of finality leaned on "extending a path can only make it longer", and a negative edge is precisely a refund that breaks that sentence. Graphs with negative weights belong to Bellman-Ford, which gives up the greedy shortcut and pays O(VE) for the generality. Knowing which tool the input demands is most of the battle in this family.

Interviews rarely hand you a textbook shortest path. They restyle the accumulator. Path with Maximum Probability multiplies edge probabilities and chases the largest product with a max-heap, and the greed survives because every factor is at most 1, so extending a path never raises its probability. The minimax family changes the question entirely: Swim in Rising Water and Path With Minimum Effort score a path by its worst single moment, not its sum, so the heap key becomes the maximum-so-far, and the first arrival still wins.

The recognition signal is "cheapest, fastest, safest path" over weighted connections, with one warning attached: an extra constraint like a stop budget breaks the finalization logic, because the cheapest path to a node may be illegal and a pricier one legal. That case shows up in the practice set below as the problem Dijkstra famously can't solve.

Five habits that separate working Dijkstras from plausible-looking ones:

Two checks first: why is a node's first extraction from the heap provably final, and which single property of the edges does that proof lean on? Start with the straight applications, then the restyled accumulators, then meet the stop-budget problem that forces a different algorithm: