Dijkstra

TL;DR

Dijkstra is BFS where the queue is a min-heap keyed by the current best known distance from the source. Pop the cheapest unsettled node, relax its outgoing edges, push any improvements back onto the heap. The first time a node comes off the heap, the distance you popped is its shortest-path cost — final, no revisions. That single fact is the whole algorithm.

It only works when every edge weight is non-negative. The greedy “first pop wins” argument falls apart the moment a negative edge can sneak in later and undercut a settled node. For graphs with negative edges, reach for Bellman-Ford (O(VE), handles negatives, detects negative cycles) or SPFA (queue-based Bellman-Ford, faster in practice but same worst case). For graphs where every edge has the same weight, plain BFS is strictly better — you pay no log V factor and the queue is just a deque.

The practical template is heapq in Python with (dist, node) tuples, a dist[] array, and lazy deletion: when you pop a tuple whose stored distance is worse than dist[node], you skip it. No decrease-key, no fancy data structures.

When to reach for it

Signals that Dijkstra is the right pattern:

• The graph has weighted edges and the question asks for a shortest, cheapest, or minimum-cost path.
• All weights are non-negative. Distances, latencies, prices, road lengths, grid heights — anything physical that can’t go below zero.
• The problem says “minimum effort”, “cheapest flight”, “fastest route”, “smallest maximum”, or “shortest time to reach”. Translate the cost function into edge weights and check that it’s monotonic in path length.
• You only need shortest paths from one source (single-source shortest path). For all-pairs on a dense graph, Floyd–Warshall is simpler.

Signals it’s not Dijkstra: negative weights anywhere (Bellman-Ford), unweighted edges (BFS), or a DAG where you can topologically sort and relax in linear time.

Flavor 1 — classic Dijkstra

Single source, sum of edge weights, non-negative.

import heapq

def dijkstra(n: int, edges: list[tuple[int, int, int]], src: int) -> list[float]:
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))  # undirected; drop for directed

    dist = [float("inf")] * n
    dist[src] = 0
    heap = [(0, src)]  # (best known distance, node)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                   # stale entry — lazy delete
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Worked example. Five nodes 0..4, undirected, edge list:

(0, 1, 4)   (0, 2, 1)   (2, 1, 2)
(1, 3, 1)   (2, 3, 5)   (3, 4, 3)

Source = 0. Initial dist = [0, ∞, ∞, ∞, ∞], heap = [(0, 0)].

Final dist = [0, 3, 1, 4, 7]. Note steps 4 and 6: the heap holds stale copies of nodes 1 and 3 with worse distances. The if d > dist[u]: continue check is what makes lazy deletion correct.

Flavor 2 — modified Dijkstra

When the path “cost” isn’t a sum but the max (or min) of edge weights along the path, the skeleton is identical — only the relaxation changes.

Path with Minimum Effort (LC 1631): in a grid, the cost of a path is the maximum absolute height difference between adjacent cells. Find the path from top-left to bottom-right that minimises this max.

def min_effort(heights: list[list[int]]) -> int:
    R, C = len(heights), len(heights[0])
    effort = [[float("inf")] * C for _ in range(R)]
    effort[0][0] = 0
    heap = [(0, 0, 0)]  # (max edge so far, r, c)

    while heap:
        e, r, c = heapq.heappop(heap)
        if e > effort[r][c]:
            continue
        if (r, c) == (R - 1, C - 1):
            return e
        for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C:
                ne = max(e, abs(heights[nr][nc] - heights[r][c]))
                if ne < effort[nr][nc]:
                    effort[nr][nc] = ne
                    heapq.heappush(heap, (ne, nr, nc))
    return 0

The relaxation ne = max(e, edge_weight) replaces nd = d + w. Swim in Rising Water (LC 778) is the same shape with max(t, grid[nr][nc]). The greedy invariant still holds because max is monotonic non-decreasing along a path — extending a path can only keep the cost the same or raise it, which is exactly the property Dijkstra needs.

Why it works — the invariant

Claim: the first time a node u is popped from the heap, dist[u] is its true shortest-path cost from the source.

Proof sketch. Suppose for contradiction that when we pop u with distance d, there exists a strictly shorter path P from src to u with cost d* < d. Walk along P from the source until you hit the first node x that is not yet settled (such an x exists because u itself is on P and unsettled). The predecessor of x on P is settled, so when we relaxed it we pushed (dist[x], x) onto the heap with dist[x] ≤ cost-of-P-up-to-x ≤ d*. But dist[x] ≤ d* < d means x should have come out of the heap before u. Contradiction.

The argument requires cost-of-P-up-to-x ≤ d* — i.e., extending a path never decreases its cost. Non-negative weights (or non-decreasing path costs in the modified flavor) is exactly what gives us that. A negative edge after x could make d* < cost-of-P-up-to-x, the inequality flips, and the proof collapses. That’s why Dijkstra silently returns wrong answers on negative-edge graphs — no error, just bad numbers.

Complexity

• Time: O((V + E) log V) with a binary heap. Each edge causes at most one push, each push/pop is O(log V), and lazy deletion adds at most a constant factor of stale entries.
• Time: O(E + V log V) with a Fibonacci heap thanks to O(1) amortised decrease-key. Almost never used in practice — the constants are awful and binary heaps win on real graphs.
• Space: O(V + E) for the adjacency list, O(V) for dist, and up to O(E) for the heap because we lazily leave stale entries in.

For dense graphs (E ≈ V²) an array-based O(V²) Dijkstra without a heap is actually competitive — fewer pointer chases, no log factor.

Common pitfalls

• Using Dijkstra on negative edges. It will run, return numbers, and some of those numbers will be wrong. No exception, no warning. Always check the weight constraint before reaching for heapq.
• Forgetting the stale-entry skip. If you don’t continue when d > dist[u], you’ll relax neighbours from outdated distances, push more stale entries, and either time out or return wrong answers. The if d > dist[u]: continue line is non-negotiable.
• Marking visited on push, not on pop. A common bug is to set visited[v] = True the moment you push (nd, v). Now you’ll never relax v again even if a cheaper path is found later. Mark settled after popping (or skip the visited array entirely and rely on the stale-distance check).
• Mutating the heap while iterating. Python’s heapq doesn’t support decrease-key. Don’t try to find and rewrite an entry — just push a new (better_dist, node) and let lazy deletion drop the old one.
• Paying log V for an unweighted graph. If every edge has weight 1, use BFS with a deque. Dijkstra still gives the right answer but you’re burning a heap operation per edge for no reason.

Where you see this in production

• OSPF (Open Shortest Path First). The interior gateway routing protocol every backbone router runs computes shortest paths over its link-state database with Dijkstra. Edge weights are configured link costs (typically inverse bandwidth).
• OSRM and Google Maps short-distance routing. For trip distances short enough that the road graph fits in working memory, classic Dijkstra (often bidirectional Dijkstra, which expands from both ends and meets in the middle) computes turn-by-turn routes. Long-distance routing layers contraction hierarchies on top, but the bottom of the stack is still Dijkstra.
• Package manager version solvers. pip, cargo, and uv model dependency resolution as a graph search where edge “cost” encodes how far a candidate version is from the user’s preferred constraint; Dijkstra-style relaxation picks the resolution with minimum total distance from the ideal.
• Network diagnostics — iperf and traceroute path discovery. Tools that infer the latency-minimising path through a measured network mesh run Dijkstra over a per-hop latency matrix to suggest the route a TCP flow should hug.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.
• William Fiset — Dijkstra — www.youtube.com