Shortest Path Algorithms

The cheapest route from A to B, found without trying every route: settle nodes in order of distance and never revisit a settled one.

Dijkstra settles four nodes in order A, B, C, D with distances 0, 1, 3, 6 along the cheapest route A to D

Why Does This Exist?

Routing, scheduling, dependency resolution, and alignment all reduce to cheapest paths on weighted graphs: fewest hops, lowest latency, smallest edit cost. Trying every route explodes combinatorially, yet the answer has structure: any subpath of a shortest path is itself shortest, so distances can be built outward rather than enumerated. The graph encoding lives in graph fundamentals; the cost language lives in complexity analysis.

The one idea you need first

Relaxation: if reaching $u$ costs $d[u]$ and edge $u \to v$ costs $w$ , then $v$ is reachable for $d[u] + w$ , so $d[v] = \min(d[v], d[u] + w)$ . Every algorithm below repeats relaxation in a deliberate order until no distance improves.

Think of It Like This

Ripples from a dropped stone

Drop a stone in a pond with an uneven bottom: the ripple reaches nearby shallows first, then spreads outward, always expanding the closest unreached point next. Once the water at some spot starts moving, no later ripple can arrive sooner. Every other route goes through water the ripple reached even later, so the first arrival is the fastest possible.

Dijkstra is that ripple on a graph with non-negative depths. Negative edges are whirlpools that pull the ripple backward in time and break the first-arrival guarantee, which is why they need a different method that re-checks everything.

Where the analogy stops: implementations use priority queues for the expansion order and edge lists for sparse graphs, not water.

How It Actually Works

BFS fits unweighted graphs: layer outward from the source, and first visit is shortest in hops. Cost grows with nodes plus edges.

Dijkstra fits weights $\ge 0$ : keep tentative distances, repeatedly settle the unsettled node with the smallest tentative distance, then relax its edges. Settling order is final because any alternative route detours through an unsettled node at least as far away. Cost is $O((n + m) \log n)$ with a heap, where $n$ counts nodes and $m$ counts edges.

Bellman-Ford fits any weights with no reachable negative cycle: relax every edge $n - 1$ times, then one more improving pass proves a negative cycle exists. Cost is $O(nm)$ , slower but general.

For all pairs, Floyd-Warshall suits dense small graphs, while repeated Dijkstra or Johnson with reweighting suits sparse ones. A-star adds a heuristic when one target matters.

Worked example

Nodes A, B, C, D with A to B $1$ , A to C $4$ , B to C $2$ , B to D $6$ , C to D $3$ . Source A.

Start $d = (0, \infty, \infty, \infty)$ . Settle A ( $0$ ): relax B to $1$ , C to $4$ . Settle B ( $1$ , smallest unsettled): relax C to $\min(4, 1+2) = 3$ , D to $1+6 = 7$ . Settle C ( $3$ ): relax D to $\min(7, 3+3) = 6$ . Settle D ( $6$ ).

Distances are $(0, 1, 3, 6)$ with parents A, A, B, C. The cheapest A to D path is A to B to C to D costing $1 + 2 + 3 = 6$ , beating A to B to D at $7$ and A to C to D at $7$ .

Code

The point is the settling order, not the heap. This runs Dijkstra on the worked graph and prints the distances the hand trace found.

1import heapq2
3def dijkstra(start: str, edges: dict[str, list[tuple[str, int]]]) -> dict[str, int]:4    dist: dict[str, int] = {start: 0}  # best known cost so far5    pq: list[tuple[int, str]] = [(0, start)]  # frontier ordered by cost6    while pq:7        d, u = heapq.heappop(pq)  # smallest unsettled node settles next8        if d > dist.get(u, 10**18):9            continue  # stale entry, a better one already won10        for v, w in edges.get(u, []):11            nd = d + w  # relax edge u to v12            if nd < dist.get(v, 10**18):13                dist[v] = nd14                heapq.heappush(pq, (nd, v))15    return dist16
17
18edges: dict[str, list[tuple[str, int]]] = {"A": [("B", 1), ("C", 4)], "B": [("C", 2), ("D", 6)], "C": [("D", 3)]}19print(dijkstra("A", edges))  # -> {'A': 0, 'B': 1, 'C': 3, 'D': 6}

Settling order A, B, C, D with distances 0, 1, 3, 6 matches the hand computation exactly.

Watch Out For

Feeding negative edges to Dijkstra

One negative edge breaks the settling guarantee: a settled node can still improve through the negative edge later, but Dijkstra never revisits it. Reported distances come back wrong with no warning, and every path built on them inherits the error.

Symptom: Bellman-Ford finds cheaper distances on recheck, or inspection finds a path cheaper than Dijkstra's answer. Fix: use Bellman-Ford whenever negativity is possible, and assert non-negativity at input boundaries rather than assuming it.

Overflow and float fog on long paths

Summing thousands of weights in int32 wraps silently, while comparing float path costs with == splits hairs that rounding decided. A graph with 100,000 unit edges fits the distance but not a counter that assumed small numbers.

Symptom: negative distances on positive graphs, or nondeterministic ties between equal paths. Fix: use 64-bit integers for integral weights, infinities as proper sentinels with overflow-safe addition, and epsilon-tolerant comparison for floats.

The Quick Version

Relaxation $d[v] = \min(d[v], d[u] + w)$ is the shared engine; the order of relaxation differs.
BFS suits unweighted graphs, Dijkstra suits non-negative weights, and Bellman-Ford handles negativity and detects bad cycles.
On the worked graph, settling order A, B, C, D gives distances 0, 1, 3, 6.
Settled Dijkstra distances are final: never revisit, never improve.
Negative edges need Bellman-Ford, while long paths need 64-bit sums and careful comparison.