DijkstraSingle-source shortest paths

01Why it exists

Reach for it when you see:Shortest, fastest or cheapest path, edges with non-negative weights, costs that add up along a path, one source to every node, grids where each cell costs a different amount, a priority queue plus relaxation.

02The core idea

BFS finds shortest paths on an unweighted graph because a queue's first-in-first-out order happens to coincide with "in increasing order of distance". The moment edges carry weights that correspondence breaks: two short hops can be closer than one long one. Dijkstra swaps the queue for a min-heap and keeps, for every node, the shortest distance known so far in dist (∞ to begin with). Each round it pops the node u that is not settled yet and has the smallest dist, declares that distance final, and relaxes every edge out of it: if dist[u] + w < dist[v], lower dist[v] and record parent[v] = u. The order in which nodes get settled is exactly their order of distance from the source, nearest first.

Why is a distance final the instant the node is popped? Let u be the unsettled node with the smallest dist, and call that value d. Any path from the source to u has to step out of the settled set somewhere for the first time, arriving at some unsettled node y. The node before y is already settled, and when it was settled it relaxed y along that very edge, so reaching y costs at least dist[y], and dist[y] ≥ d. The remaining edges from y to u all have non-negative weight, so they can only make the total longer. No path is shorter than d, and that is why this greedy choice is correct. The proof leans on non-negative weights, and a negative edge breaks it outright: with A→B = 2, A→C = 3 and C→B = −2, B is settled at 2 in the second round, yet A→C→B costs only 1.

Each node is settled once, and its edges are scanned at that moment, so every edge is relaxed at most once (twice on an undirected graph, once per direction). Every successful relaxation pushes an entry, so the heap holds at most O(E) of them, each push and pop is O(log E), and since E ≤ V² we have log E ≤ 2 log V, for a total of O((V + E) log V). Space is O(V) for dist and parent. The code here uses lazy deletion: superseded entries stay in the heap and can pile up to O(E), and only a heap with decrease-key brings that back to O(V). Skipping the heap and scanning linearly for the minimum each round is O(V²), which on a dense graph where E approaches V² actually beats the heap version's O(V² log V). When there is only one destination, you can finish the moment it is popped, which in practice often touches a small part of the graph — though the worst case still walks all of it.

Three mistakes come up again and again. First, carrying over the BFS habit of marking a node visited when you push it: a node in Dijkstra can be discovered along a long route and improved by a shorter one later, so it is only final when it is popped. Second, forgetting to skip stale entries with if d > dist[u]: continue: the answer stays correct, but the same node gets expanded over and over, and dense graphs slow to a crawl. Third, storing distances in a C++ int, where the accumulated weights overflow. How it divides up the work with its neighbours: when every edge weighs 1, use BFS; when the weights are only 0 and 1, a deque-based 0-1 BFS gets O(V + E); with negative edges, use Bellman-Ford; on a DAG, sort topologically first and relax in that order for O(V + E), negative weights included; and for the distance between every pair of nodes on a small graph, use Floyd-Warshall. Prim's minimum spanning tree looks almost identical to Dijkstra, and the only difference is that its heap compares the weight of a single edge rather than the distance accumulated from the source.

03The algorithm

1. 1Build the adjacency list adj[u] = [(v, w), …], adding each edge in both directions for an undirected graph. Confirm that every weight is ≥ 0; a single negative one rules Dijkstra out.
2. 2Set every dist to ∞ and every parent to −1, then dist[src] = 0 and push (0, src) onto the min-heap.
3. 3Pop the top of the heap, (d, u). If d > dist[u] this is a stale entry that has since been improved, so skip it; otherwise dist[u] is final from here on. With a single destination, you can stop as soon as u is that destination.
4. 4For each edge (v, w) out of u: if d + w < dist[v], set dist[v] = d + w and parent[v] = u, then push (dist[v], v). There is no need to delete v's older entry from the heap.
5. 5Repeat 3–4 until the heap is empty. A node still at ∞ is unreachable; for the route itself, follow parent back from the destination until you reach −1, then reverse the sequence.

04Interactive demo

An undirected graph of six junctions A–F, where the number on each edge is how many minutes that stretch of road takes. The source is A, and it is the same graph as the code example. Node colours follow the legend: yellow is still in the priority queue, blue is the node just popped and currently relaxing its edges, and a finished node becomes a filled "settled" circle. The edge under inspection turns yellow, and it is drawn dashed when nothing was updated; the blue edges are the shortest-path tree so far. Watch B: it starts at 4 straight from A, then drops to 2 + 1 = 3 once C is settled, while the old (4, B) stays in the queue and is struck through and skipped when its turn comes. D and E are each improved once as well. After E is settled, trying E–F gives 10 + 5 = 15, no better than 14, so nothing changes. The last step highlights A → C → B → D → F in green, 14 minutes in all.

05Code

Three functions: the lazy-deletion heap version of Dijkstra (which records parent at the same time), the reconstruction of a path by following parent, and the heap-free O(V²) adjacency-matrix version that scans for the minimum each round. Both versions produce the same distances, and they sit side by side for comparison: reach for the heap version on sparse graphs, and for the matrix version when there are few nodes but almost every pair is connected.

import heapq
from math import inf


def dijkstra(adj, src):
    """adj[u] = [(v, w), ...] with every w >= 0. Returns (dist, parent). O((V + E) log V)"""
    n = len(adj)
    dist = [inf] * n
    parent = [-1] * n
    dist[src] = 0
    heap = [(0, src)]                       # (distance so far, node)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:                     # stale entry: u was settled with a shorter distance
            continue
        # dist[u] is final here; for a single target, add if u == target: break
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:                # relaxation succeeded
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))   # leave the stale entry in; skip it when it pops
    return dist, parent


def build_path(dist, parent, target):
    """Walk back from the target along parent, then reverse. Returns [] when unreachable"""
    if dist[target] == inf:
        return []
    path = []
    while target != -1:
        path.append(target)
        target = parent[target]
    return path[::-1]


def dijkstra_dense(mat, src):
    """Matrix version; mat[u][v] = inf means no edge. Linear scan for the minimum each round, O(V²)"""
    n = len(mat)
    dist = [inf] * n
    done = [False] * n
    dist[src] = 0
    for _ in range(n):
        u = min((i for i in range(n) if not done[i]), key=lambda i: dist[i])
        if dist[u] == inf:                  # everything left is unreachable
            break
        done[u] = True
        for v in range(n):
            if dist[u] + mat[u][v] < dist[v]:
                dist[v] = dist[u] + mat[u][v]
    return dist


if __name__ == "__main__":
    names = "ABCDEF"                        # the same graph as the interactive demo
    roads = [(0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8),
             (2, 4, 10), (3, 4, 2), (3, 5, 6), (4, 5, 5)]
    adj = [[] for _ in names]
    mat = [[inf] * len(names) for _ in names]
    for u, v, w in roads:                   # undirected: add each edge in both directions
        adj[u].append((v, w))
        adj[v].append((u, w))
        mat[u][v] = mat[v][u] = w

    dist, parent = dijkstra(adj, 0)
    print(dist)                             # [0, 3, 2, 8, 10, 14]
    path = build_path(dist, parent, 5)
    print(" → ".join(names[i] for i in path))   # A → C → B → D → F
    print(dijkstra_dense(mat, 0))           # [0, 3, 2, 8, 10, 14]

06Practice

• LeetCode 743Network Delay Time (the template problem: shortest distance to the farthest node)Medium
• LeetCode 1514Path with Maximum Probability (probabilities multiply, so use a max-heap)Medium
• LeetCode 1631Path With Minimum Effort (on a grid, with path cost as a maximum)Medium
• LeetCode 1976Number of Ways to Arrive at Destination (count the shortest paths along the way)Medium
• LeetCode 2290Minimum Obstacle Removal to Reach Corner (weights are only 0 and 1, so 0-1 BFS works)Hard
• LeetCode 2203Minimum Weighted Subgraph With the Required Paths (run it on the reversed graph too)Hard