Lesson 28 · Trees & graphs

Weighted shortest path

📖 Walk me through it — plain English

Imagine a map of cities connected by roads, and every road has a length (a "weight"). You start in one city and want the shortest total driving distance to every other city. That is the "weighted shortest path" problem, and Dijkstra's algorithm solves it — as long as no road has a negative length. (A negative road would be like a road that magically gives you distance back; Dijkstra can't handle that, which is why the lesson keeps a backup tool, Bellman-Ford, for negative weights.)

The core idea: always expand outward from the closest unfinished city first. We keep a table dist of "best distance known so far" to each city. It starts at 0 for the source and infinity (∞, meaning "no idea yet, assume unreachable") for everyone else. We also keep a min-heap — a priority queue that always hands back its smallest item first — full of (distance, city) pairs. Whenever we find a cheaper way into a city, we write the new number into dist and toss a fresh pair onto the heap.

"Relaxing" an edge just means: check if going through the city I'm at right now gives a shorter route to a neighbor, and if so, update that neighbor. The name is old jargon — picture a stretched rubber band (the distance estimate) being allowed to shrink to a tighter value.

The everyday analogy: it's like flood water spreading from a spring. Water always fills the lowest, nearest spots first. By the time the flood reaches a city, it arrived by the shortest possible path — because any longer path would still be "behind" and hasn't gotten there yet.

One subtle trick in the code: we might push the same city onto the heap several times with different distances (each time we find something cheaper). When we pop one, we check if d > dist[u]: continue — if the distance we pulled out is bigger than the best we've already recorded, this pair is a stale leftover from before, so we skip it. That's cheaper than trying to hunt down and delete old entries inside the heap.

Let's trace a tiny graph. Cities A, B, C, D. Roads (one-way for simplicity): A→B costs 4, A→C costs 1, C→B costs 2, C→D costs 5, B→D costs 1. We start at A. Each row below is the dist table for A, B, C, D — green = finalized shortest, blue = the city whose estimate we just changed, struck-through = a value we just improved away from.

Step 1 · Setup. dist[A]=0, everyone else ∞. Heap holds just (0, A).

B∞

C∞

D∞

Step 2 · Pop the smallest: (0, A). Relax A's roads. A→B: 0+4=4 < ∞, set B=4. A→C: 0+1=1 < ∞, set C=1. A is now done (green). Heap: (1,C),(4,B).

D∞

Step 3 · Pop the smallest now: (1, C). Relax C's roads. C→B: 1+2=3 < 4, so B improves from 4 to 3. C→D: 1+5=6 < ∞, set D=6. C is done. Heap: (3,B),(4,B stale),(6,D).

Step 4 · Pop (3, B). Check: 3 is NOT bigger than dist[B]=3, so it's fresh — process it. Relax B→D: 3+1=4 < 6, so D improves from 6 to 4. B is done. Heap: (4,B stale),(4,D),(6,D stale).

Step 5 · Pop (4, B) — the stale leftover. Check: 4 > dist[B]=3, so skip it (the struck-through 4 is the old value we abandoned). No work done.

Step 6 · Pop (4, D): fresh (4 = dist[D]). D has no outgoing roads, so nothing to relax. Then pop (6, D): 6 > dist[D]=4, stale, skip. Heap empty — done. Final shortest distances from A:

Notice the payoff: the direct road A→B was length 4, but the detour A→C→B totaled only 3. Dijkstra found that automatically because it expanded C (distance 1) before settling B. And the final route to D is A→C→B→D = 1+2+1 = 4, beating the more obvious A→C→D = 6.

Why it works: because all weights are non-negative, the first time we pop a city off the heap, its recorded distance is already the true shortest — no later path can sneak in cheaper, since every remaining path is at least as long as what's already in the heap. Why the complexity is O((V + E) log V) (V = number of cities, E = number of roads): we may push a heap entry per edge (E of them), and each heap push or pop costs log of the heap size, which is bounded by the number of cities. The stale-skip trick keeps wasted pops cheap. Bellman-Ford, the negative-weight fallback, instead loops over all edges V−1 times — O(V · E), noticeably slower — so you only reach for it when a weight might actually be negative.

BFS gives shortest path on unweighted graphs. Dijkstra is the weighted generalization — but only with non-negative weights. Bellman-Ford handles negatives (and detects negative cycles).

Interactive — step through Dijkstra

Click "Step" to relax the next edge.

Dijkstra — algorithm

Initialize dist[source] = 0, others = ∞.
Push (0, source) into a min-heap.
Pop the smallest-distance node. If we've already finalized it, skip.
For each neighbor v, if dist[u] + w(u,v) < dist[v], update and push.
Repeat until heap is empty.

import heapq

def dijkstra(graph, src):
    # graph: adjacency list {u: [(v, weight), ...]}
    dist = {u: float('inf') for u in graph}
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:        # stale entry; skip
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

Complexity: O((V + E) log V) with a binary heap.

Bellman-Ford — when there are negative weights

def bellman_ford(n, edges, src):
    dist = [float('inf')] * n; dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # one more pass — if anything still relaxes, a negative cycle is reachable
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None
    return dist

O(V · E). Slower than Dijkstra; only reach for it when weights might be negative.

Network delay time — run Dijkstra and return when the last node hears the signal:

→ Going deeper: Graph shortest paths generalize dependency ordering. See Topological sort.

→ Going deeper: Dijkstra is weighted BFS — when all edges cost 1, use BFS / DFS instead. See BFS / DFS.