Dijkstra's Algorithm

What is this?

BFS finds the shortest path when every step costs the same, but real roads aren't like that — some stretches are long, some are quick. Dijkstra's algorithm is the upgrade for maps where each connection has a length or cost. It works like a patient explorer who always visits the nearest unexplored place next: settle the closest spot first, note any shortcuts it reveals, and repeat. Because you never look at a faraway place before a nearer one, the first time you lock in a spot, you've already found its cheapest route.

💡 Fun fact: Edsger Dijkstra invented this algorithm in 1956 — and in about twenty minutes, in his head, while sitting at a café in Amsterdam with his fiancée, no pen or paper. He later said the lack of writing materials forced him to keep it simple, which is exactly why it turned out so elegant. Your GPS still runs a descendant of those twenty minutes.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: to find the shortest path from one source to every other node in a graph with non-negative weights, repeatedly settle the closest unsettled node and relax its edges. Because no edge can ever make a path cheaper, the first time you pop a node off a min-heap you already hold its final shortest distance — a greedy choice that's provably optimal. It's BFS upgraded for weighted graphs.

1. What "single-source shortest path" really means

You have a weighted graph and a start node s. You want dist[v] — the cheapest total weight to reach every v from s. The naive idea (try all paths) is exponential. Dijkstra makes it tractable with one invariant:

Process nodes in increasing order of their distance from the source. Maintain a tentative dist[], all ∞ except dist[s] = 0. Pull the smallest tentative distance off a min-heap, mark it settled, and relax its outgoing edges:

The key guarantee: once a node is popped, its distance is final. With non-negative weights, every other route to it must pass through nodes already at least that far away, so it can't be improved.

⚠️ This is exactly where negative weights break Dijkstra. A later, cheaper edge could undercut an already-settled node — but it's been frozen. For negative edges you need Bellman-Ford (O(V·E), handles negatives, detects negative cycles).

2. Where you'll actually meet this

Shortest-path-on-weighted-graphs is one of the most deployed algorithms in production:

• Network routing. OSPF (Open Shortest Path First), the backbone interior-gateway protocol, runs Dijkstra over a link-state map where edge weights are link costs. Each router computes shortest paths to every subnet.
• Maps & GPS. Driving/transit directions are shortest paths where weights are travel time or distance. Production systems layer A* (Dijkstra + a goal heuristic) and contraction hierarchies on top, but the core is Dijkstra.
• Latency-aware / cost-aware routing. Service meshes and CDNs route requests along least-latency or least-cost paths; weights are measured RTTs or egress prices.
• Games & robotics. Pathfinding on weighted terrain (mud costs more than road); A* is the genre standard, Dijkstra its uniform-cost special case.
• Finance & ops research. Cheapest currency-conversion or transport routes — modeled as min-cost paths over weighted graphs.

If a problem says shortest / fastest / cheapest path, minimum time to reach, non-negative weights — this is your tool.

3. The Dijkstra toolkit

1. Min-heap as the engine. A priority queue keyed on tentative distance gives you the closest unsettled node in O(log V). This is what makes it O((V + E) log V) instead of O(V²).
2. Lazy deletion. Heaps can't cheaply update a key, so just push duplicates on every improvement and skip stale pops (if d > dist[u]: continue). Simpler and fast in practice.
3. Relaxation only forward. When you settle u, try to improve each neighbour v. Never relax into already-settled nodes — their distances are final.
4. Settle-on-pop, not on-push. A node's distance is committed the moment it leaves the heap, not when first discovered. This ordering is the correctness proof.
5. Reconstruct paths via parents. Store prev[v] on each successful relaxation; walk back from target to source to recover the actual route, not just its length.

The canonical heap implementation:

import heapq

def dijkstra(graph, source, n):
    # graph[u] = list of (neighbor, weight), weights >= 0
    dist = [float('inf')] * n
    dist[source] = 0
    pq = [(0, source)]                  # (tentative_distance, node)

    while pq:
        d, u = heapq.heappop(pq)        # closest UNSETTLED node

        if d > dist[u]:
            continue                    # stale duplicate — already settled cheaper

        for v, w in graph[u]:           # relax every outgoing edge
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))   # lazy: push, don't decrease-key

    return dist                          # dist[v] = shortest distance source -> v

4. A 30-second worked example

Source A, find shortest distances:

Notice C was tentatively 7 via B, then improved to 5 via D→E. That late improvement is fine because C hadn't been popped yet — relaxation kept refining it until it was settled.

5. Problems / when to reach for it

• Network Delay Time — time for a signal from one node to reach all nodes = the maximum of Dijkstra's shortest distances (and ∞ if any node is unreachable).
• Path with Maximum Probability — multiply probabilities along edges; take -log(p) as the weight so "most probable" becomes "shortest," then run Dijkstra (all weights non-negative since 0 ≤ p ≤ 1).
• Cheapest Flights within K Stops — Dijkstra variant with a hop budget (often better solved with Bellman-Ford-style relaxation rounds).
• Reach for Dijkstra whenever weights are non-negative and you need shortest paths from one source. Target: O((V + E) log V) time, O(V) space.

6. Common pitfalls 🚫

• Negative weights. Dijkstra fails silently — it returns wrong answers, not an error. Use Bellman-Ford (or SPFA) when any edge is negative.
• Forgetting lazy-deletion / settled check. Without if d > dist[u]: continue, you reprocess stale heap entries, inflating runtime (and sometimes redundantly relaxing).
• Tuple order in the heap. Distance must be the first element so the heap orders by distance, not node id.
• Using BFS on a weighted graph. Plain BFS counts edges, not weight — correct only when every edge weight is equal. Otherwise you need Dijkstra (or 0-1 BFS for weights in {0,1}).
• Not handling unreachable nodes. Disconnected vertices stay at ∞; decide whether that's a valid answer or a -1/error per the problem.

7. Key takeaways

1. Greedy + min-heap, settle the closest first. The first pop of a node is its final shortest distance — that's the whole algorithm and its proof.
2. Relaxation is the operation: dist[v] = min(dist[v], dist[u] + w), applied forward from each settled node.
3. Non-negative weights are mandatory. Negative edges silently break the greedy invariant → switch to Bellman-Ford.
4. It's weighted BFS. Equal weights ⇒ BFS suffices; differing weights ⇒ Dijkstra; known goal + heuristic ⇒ A*.
5. O((V + E) log V) with a binary heap, the version you should reach for in interviews — and the version OSPF and your GPS quietly run millions of times a day.