Dijkstra's shortest path

What this chapter covers

Every traversal so far treated an edge as a single equal step, and on that assumption breadth-first search was the shortest-path algorithm: fewest edges meant shortest. Real graphs break the assumption. Roads have lengths, network links have latencies, flights have fares — edges carry weights, and once they do, the path with the fewest edges is often not the cheapest one. A single long-haul edge can cost more than a detour of three short ones. Dijkstra's algorithm is the fix, and the fix is small: swap breadth-first search's plain queue for a priority queue — the binary heap from the heaps chapter — and always expand the node that is closest by total weight rather than by hop count. This chapter builds it, watches it settle a small weighted graph one node at a time, and shows it finding a route a third the cost of the fewest-hops path breadth-first search would pick.

A bit of history

Edsger Dijkstra devised the algorithm in 1956 and published it in 1959, and the story of its invention is famous because he told it so plainly: he worked it out in about twenty minutes, in his head, over coffee with his fiancée on a café terrace in Amsterdam, as a demo of the routing power of the ARMAC computer. He deliberately avoided pencil and paper so the solution would have to be simple enough to explain, which is why the algorithm is as clean as it is. The original 1959 formulation had no heap — it scanned all vertices each round to find the closest, giving $O(V^2)$ — and that form is still the best choice for dense graphs. The $O((V+E)\log V)$ version most people mean by "Dijkstra" today came later, once binary heaps and then Fibonacci heaps (Fredman and Tarjan, 1984) gave a faster way to repeatedly extract the minimum. The core idea, though, is entirely Dijkstra's and entirely 1956: greedily settle the nearest node, and because weights are non-negative, its distance is final the moment you reach it.

The intuition

Keep a tentative distance for every node — zero for the source, infinity for everything else — and a priority queue ordered by that distance. Repeatedly pull out the node with the smallest tentative distance. Here is the key claim: because every edge weight is non-negative, that node's tentative distance is now its true shortest distance and can never improve, so we "settle" it permanently. Any other route to it would have to pass through some node still in the queue, which is at least as far away, and then travel further — so it can't be shorter. This is exactly breadth-first search's "first discovery is optimal," but measured in accumulated weight instead of hop count.

Having settled a node, we relax its edges: for each neighbor, check whether reaching it through the just-settled node is cheaper than its current tentative distance, and if so, lower it and push the improved entry onto the queue. The queue may end up holding several entries for the same node at different distances — that's fine and simpler than trying to update in place; when we pop a stale one (a distance worse than the node's now-settled value) we just skip it. The whole algorithm is breadth-first search with the FIFO queue replaced by a min-heap, plus the relaxation step. That one substitution — queue to priority queue — is the difference between "nearest by hops" and "cheapest by weight."

Complexity: how it scales

With a binary heap, Dijkstra is $O((V + E)\log V)$: each of the $V$ vertices is extracted once ($\log V$ each), and each of the $E$ edges can trigger a push ($\log V$ each). The heapless 1959 version is $O(V^2)$ because each round linearly scans all vertices for the minimum; it wins only when the graph is dense enough that $E \approx V^2$ and the $\log$ factor stops helping. Space is $O(V)$ for the distance and parent arrays plus the heap. But the number that matters for choosing Dijkstra isn't its speed — it's the cost of the path it finds versus what breadth-first search would give you on the same weighted graph:

On 400-vertex weighted graphs, the fewest-hops path breadth-first search picks averaged about 25% more total cost than Dijkstra's cheapest path — and that's the average case, where random weights partly wash out. In the worst case the gap is unbounded: the animation below has breadth-first search taking a single direct edge of weight 10 when a three-edge detour costs only 3, a route more than three times as expensive. That's the point of the whole chapter. The moment edges have weights, breadth-first search stops answering the question you're actually asking, and Dijkstra is what answers it.

What it's good at, what it isn't

Dijkstra is the right tool for cheapest-cost paths from a source when edge weights are non-negative, which covers most of the weighted-path problems you meet: road distances, travel times, network latencies, transmission costs, cheapest sequences of operations. It's efficient, it's a single clean pass, and with a heap it scales to large sparse graphs. It also generalizes: A* (a later chapter) is Dijkstra plus a heuristic that steers it toward a goal, and a min-priority-queue traversal of exactly this shape underlies Prim's minimum spanning tree.

Its hard requirement is non-negative weights. A single negative edge can make settling-on-pop incorrect, because a cheaper route might arrive after a node was already finalized — that's the Bellman-Ford case next chapter. Dijkstra also computes distances from one source; for all-pairs distances you either run it from every vertex or switch to Floyd-Warshall. And it finds the cheapest path, which isn't always the fewest-hops path — if hop count is what you care about (fewest transfers, fewest intermediaries), plain breadth-first search is both correct and faster, because there Dijkstra's heap is wasted overhead.

The data, or the inputs

The face-off runs on random weighted graphs (edge weights 1–20) and compares, for random node pairs, the total cost of Dijkstra's cheapest path against the cost of the fewest-hops path breadth-first search finds — isolating the effect of ignoring weights. The correctness check confirms the heap version's distances exactly match the trusted $O(V^2)$ reference on hundreds of graphs, and that every reconstructed path's edge weights sum to its reported cost. The animation runs Dijkstra on a small weighted graph rigged so the direct edge is a trap: the numbers inside the nodes are their tentative distances, so you can watch them fall as edges relax and freeze as nodes settle.

Build it, one function at a time

The core algorithm — a min-heap, settle-on-pop, relax the edges:

def dijkstra(adj, start):
    """Cheapest-cost distances from `start` over non-negative weighted edges. `adj[u]` is a
    list of (neighbor, weight). Keep a tentative distance for every node and a min-heap of
    (distance, node). Repeatedly pop the closest unsettled node — its distance is now final —
    and RELAX each outgoing edge: if going through u reaches v more cheaply, lower v's
    tentative distance and push the improved entry. O((V+E) log V) with a binary heap.
    Returns (dist, parent); parent lets you rebuild the actual path."""
    n = len(adj)
    dist = [float("inf")] * n
    parent = [-1] * n
    dist[start] = 0
    pq = [(0, start)]                       # (tentative distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                        # a stale, superseded entry — skip it
        for v, w in adj[u]:
            nd = d + w                       # cost to reach v via u
            if nd < dist[v]:                 # relaxation: found a cheaper way to v
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, parent

Reconstructing the actual cheapest path from the parent pointers:

def shortest_path(adj, start, target):
    """Rebuild the cheapest path start → target by walking parents back, then reversing.
    Returns (path, cost), or (None, inf) if the target is unreachable."""
    dist, parent = dijkstra(adj, start)
    if dist[target] == float("inf"):
        return None, float("inf")
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1], dist[target]

And breadth-first search's answer to the same question, to show why it's wrong once edges have weight:

def bfs_fewest_hops(adj, start, target):
    """BFS's answer to the same question, to show why it's the WRONG tool once edges have
    weights: it finds the path with the fewest EDGES, ignoring their cost. We then total the
    real weights along that fewest-hop path — usually more expensive than Dijkstra's."""
    from collections import deque
    n = len(adj)
    parent = [-1] * n
    seen = [False] * n
    seen[start] = True
    q = deque([start])
    while q:
        u = q.popleft()
        for v, _w in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                q.append(v)
    if not seen[target]:
        return None, float("inf")
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    path.reverse()
    cost = 0
    wof = {(u, v): w for u in range(n) for v, w in adj[u]}
    for a, b in zip(path, path[1:]):
        cost += wof[(a, b)]
    return path, cost

Watch it work

Here's Dijkstra on a small weighted graph, starting at node 0 (the target is node 6, far right). The number inside each node is its current tentative distance — it starts at ∞ for everything but the source, and falls as edges relax. Orange is the node being settled this step; green nodes are settled (distance final); blue nodes are in the frontier (a finite tentative distance, still improvable); dark nodes are untouched. The grey numbers on the edges are their weights. Watch node 6: the direct edge 0→6 has weight 10, but Dijkstra never takes it, because settling 1, then 3, reveals the detour 0→1→3→6 costs only 3. The cheapest path isn't the one with the fewest edges — it's the one the priority queue uncovers by always chasing the smallest running total:

The complete code

The from-scratch tab is Dijkstra with a heap, path reconstruction, and the BFS-hops contrast; the library tab is the $O(V^2)$ reference the traces are checked against, with the networkx calls you'd actually use noted at the top. Flip between them.

"""Dijkstra's algorithm — shortest paths in a graph whose edges have non-negative
weights. This is the moment the "every edge is one step" assumption of BFS breaks.
On a road map, a route with more turns can be shorter in miles; on a network, more hops
can mean less latency. When edges carry weights, "fewest edges" is no longer "cheapest,"
and BFS's shortest-path guarantee evaporates.

Dijkstra fixes it with one change: replace BFS's plain FIFO queue with a PRIORITY queue
(the binary heap from the heaps chapter). Instead of expanding the nearest node by
hop-count, always expand the nearest node by total WEIGHT so far. Because edge weights are
non-negative, the first time we pull a node off the priority queue we have its true
cheapest distance — the same "first discovery is optimal" guarantee as BFS, now measured
in cost rather than hops. That's the whole idea: BFS with a heap.
"""
import heapq


# region: dijkstra
def dijkstra(adj, start):
    """Cheapest-cost distances from `start` over non-negative weighted edges. `adj[u]` is a
    list of (neighbor, weight). Keep a tentative distance for every node and a min-heap of
    (distance, node). Repeatedly pop the closest unsettled node — its distance is now final —
    and RELAX each outgoing edge: if going through u reaches v more cheaply, lower v's
    tentative distance and push the improved entry. O((V+E) log V) with a binary heap.
    Returns (dist, parent); parent lets you rebuild the actual path."""
    n = len(adj)
    dist = [float("inf")] * n
    parent = [-1] * n
    dist[start] = 0
    pq = [(0, start)]                       # (tentative distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                        # a stale, superseded entry — skip it
        for v, w in adj[u]:
            nd = d + w                       # cost to reach v via u
            if nd < dist[v]:                 # relaxation: found a cheaper way to v
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, parent
# endregion


# region: shortest_path
def shortest_path(adj, start, target):
    """Rebuild the cheapest path start → target by walking parents back, then reversing.
    Returns (path, cost), or (None, inf) if the target is unreachable."""
    dist, parent = dijkstra(adj, start)
    if dist[target] == float("inf"):
        return None, float("inf")
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1], dist[target]
# endregion


# region: bfs_hops
def bfs_fewest_hops(adj, start, target):
    """BFS's answer to the same question, to show why it's the WRONG tool once edges have
    weights: it finds the path with the fewest EDGES, ignoring their cost. We then total the
    real weights along that fewest-hop path — usually more expensive than Dijkstra's."""
    from collections import deque
    n = len(adj)
    parent = [-1] * n
    seen = [False] * n
    seen[start] = True
    q = deque([start])
    while q:
        u = q.popleft()
        for v, _w in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                q.append(v)
    if not seen[target]:
        return None, float("inf")
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    path.reverse()
    cost = 0
    wof = {(u, v): w for u in range(n) for v, w in adj[u]}
    for a, b in zip(path, path[1:]):
        cost += wof[(a, b)]
    return path, cost
# endregion

"""The library counterpart. In practice you'd use networkx, whose `dijkstra_path` and
`single_source_dijkstra` are the same algorithm with a polished API:

    import networkx as nx
    G = nx.DiGraph()
    for u in range(n):
        for v, w in adj[u]:
            G.add_edge(u, v, weight=w)
    length, path = nx.single_source_dijkstra(G, source)   # dict of costs, dict of paths

networkx uses a binary heap exactly like impl.py. To keep this chapter's data
reproducible with the standard library alone, the trace generator checks our heap-based
Dijkstra against the simple O(V^2) reference below — the original 1959 formulation, which
scans for the closest unsettled node each round instead of using a heap. Same answers,
worse asymptotics; it's the ground truth, not the thing you'd ship.
"""


# region: reference
def dijkstra_dense(adj, start):
    """Dijkstra's original O(V^2) form: no heap. Each of V rounds linearly scans for the
    unsettled node with the smallest tentative distance, settles it, and relaxes its edges.
    Simple and correct — the trusted reference our heap version must match. Faster than the
    heap version only on very dense graphs (E close to V^2), where the heap's log factor
    stops paying off."""
    n = len(adj)
    dist = [float("inf")] * n
    dist[start] = 0
    settled = [False] * n
    for _ in range(n):
        u, best = -1, float("inf")
        for i in range(n):
            if not settled[i] and dist[i] < best:
                best, u = dist[i], i
        if u == -1:
            break                            # remaining nodes are unreachable
        settled[u] = True
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist
# endregion

Scratch vs library

The comparison that matters here isn't our Dijkstra against a library's — they compute identical distances, as the correctness check confirms against the $O(V^2)$ reference. It's Dijkstra against breadth-first search, and it makes a subtle point about algorithm choice. BFS and Dijkstra answer different questions — fewest hops versus cheapest cost — and on an unweighted graph those questions coincide, which is why BFS looked like "the" shortest-path algorithm two chapters ago. Weights split the questions apart, and using BFS on a weighted graph isn't slow, it's simply wrong: it optimizes the wrong quantity. The lesson repeats a theme from the BFS chapter: matching the algorithm to the problem isn't only about speed, it's about which quantity you're minimizing. Dijkstra costs a $\log V$ factor more than BFS for the privilege of respecting weights; on a weighted graph that factor buys correctness, and on an unweighted one it's pure waste. In production you'd call networkx's single_source_dijkstra; building it once shows you exactly why the heap is there and exactly when the weights make it necessary.

Where you'll actually meet it

Dijkstra is one of the most deployed algorithms in the world. Every GPS and mapping service — Google Maps, Waze, OpenStreetMap routers — runs Dijkstra or its goal-directed relative A* over road networks weighted by distance or travel time. Network routing protocols compute least-cost paths with it: OSPF, the backbone of IP routing inside large networks, is Dijkstra on a graph of link costs. It prices cheapest itineraries in flight and transit search, plans robot and game-agent paths, finds least-cost sequences in operations research, and shows up wherever "cheapest way from here to there" has weights on the edges. Its goal-directed and minimum-spanning-tree relatives — A*, Prim — are the next chapters, and both are this same priority-queue traversal with one idea added.

Takeaways

Dijkstra's algorithm finds cheapest-cost paths from a source over non-negative weighted edges by repeatedly settling the closest unsettled node with a priority queue and relaxing its edges, in $O((V+E)\log V)$. It's breadth-first search with the FIFO queue swapped for a min-heap — the single change that turns "fewest hops" into "cheapest cost," which on weighted graphs is a different and usually better answer, a third the cost in the chapter's rigged example. Its one hard requirement is non-negative weights, and the reason is exactly why the next chapter exists.

Bellman-Ford handles the case Dijkstra can't: graphs with negative edge weights, where a cheaper route can appear after a node would have been settled. It gives up Dijkstra's clever settle-once order and instead relaxes every edge repeatedly — slower, $O(VE)$, but able to cope with negatives and even to detect negative cycles, where the notion of a shortest path breaks down entirely.