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 (paths multiply with branches), 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 is in graph fundamentals; the cost language is 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 clever 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: the first arrival is the fastest possible, because every other route goes through water the ripple reached even later.

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

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

How It Actually Works

BFS (unweighted): layers outward from the source; first visit is shortest in hops. Cost linear in nodes plus edges.

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

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

All-pairs and heaps of paths. Floyd-Warshall cubes for dense small graphs; repeated Dijkstra (or Johnson with reweighting) for sparse ones. $k$ -shortest and A-star add heuristics 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 $(0, 1, 3, 6)$ with parent pointers A, A, B, C: the cheapest A to D path is A to B to C to D costing $1 + 2 + 3 = 6$ , beating direct-ish A to B to D at $7$ and A to C to D at $7$ .

Watch Out For

Feeding negative edges to Dijkstra

One negative edge breaks the settling guarantee: a settled node's distance can still improve through the negative edge later, but Dijkstra never revisits it. The reported distances are then wrong with no warning, and the error propagates to every path built on them.

Symptom: distances that improve when Bellman-Ford rechecks, or paths cheaper than Dijkstra's answer found by inspection. Fix: use Bellman-Ford (or SPFA/Johnson) 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; comparing float path costs with == splits hairs that rounding decided. A graph with 100,000 unit edges fits the distance but not the counter that assumed small numbers.

Symptom: negative distances on positive graphs (overflow), or nondeterministic tie-breaking 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; order differs.
BFS suits unweighted graphs, Dijkstra suits non-negative weights, 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; long paths need 64-bit sums and careful comparison.