Shortest path algorithms

The formula

relax(u→v):   if d(u) + w(u,v) < d(v)   then   d(v) = d(u) + w(u,v)

The one operation every shortest-path algorithm is built from. If reaching v through u beats the best route to v found so far, keep the new one. Everything else is bookkeeping about the order you try edges in.

d(v) = min over all edges u→v of [ d(u) + w(u,v) ],    d(source) = 0

Bellman's equation — the condition the finished answer satisfies. A distance table is correct exactly when no single edge can improve it. The shortest path to v is the shortest path to some neighbor plus one edge, which is dynamic programming in one line.

f(n) = g(n) + h(n)

The A* scoring rule. g(n) is the cost actually paid from the start to node n; h(n) is an estimate of what remains to the goal. Expand the frontier node with the lowest f, and the search pulls toward the goal instead of flooding in all directions.

Dijkstra (binary heap):     O((V + E) · log V)
Dijkstra (Fibonacci heap):  O(E + V · log V)
Bellman–Ford:               O(V · E)

The price list. V is nodes, E is edges. On a graph of 1,000 nodes and 10,000 edges, Bellman–Ford does on the order of 10⁷ relaxations; heap-based Dijkstra does roughly 10⁵ operations. You pay the hundred-fold premium for exactly one thing: tolerance of negative edge weights.

Where you meet it

The router rack in your lab. Every OSPF and IS-IS router runs Dijkstra over the link-state database each time the topology changes — the protocol spec calls the route calculation "the Dijkstra algorithm" by name ^[9]. RIP, the older protocol still living in small test networks, is a distributed Bellman–Ford where each router relaxes against its neighbors' advertised tables ^[10]. When a range network takes thirty seconds to reconverge after a switch reboot, you are watching distance-vector relaxation propagate one hop per update cycle.
The PCB autorouter and the harness table. Maze routers and their descendants are shortest-path searches over a grid, with edge weights encoding trace length, via penalties, and keep-out costs. When the autorouter takes a detour you don't like, the fix is usually re-weighting edges, not overriding the route.
Mission and route planning. A UAV path planner threading terrain masking and threat rings is A* over a cost surface; so is the pathfinding in every game engine your simulation group borrowed. The straight-line distance to the waypoint is the classic admissible heuristic — geography never beats the crow.
The review board question. "What's the worst-case telemetry latency if node 7 drops?" is a shortest-path query on the network graph with the failed links removed. Answering it by inspection works on five nodes and quietly fails on fifty; running the algorithm is the difference between an answer and a guess.

How it works

All three algorithms are the same relaxation primitive with different scheduling. The scheduling is where the correctness guarantees, the speed, and the failure modes all live.

Dijkstra is greedy. Keep a frontier of tentative distances, repeatedly settle the unsettled node with the smallest one, and relax its outgoing edges. The correctness argument has one load-bearing assumption: once the closest node is settled, no future path can undercut it — which is only true if every edge weight is non-negative. Each node settles once, so with a heap the whole run costs about (V+E)·log V.

The negative-weight trap is the mistake that actually bites. Take three nodes: A→B costs 2, A→C costs 5, C→B costs −4. Dijkstra settles B at distance 2 and never reconsiders it; the true shortest path A→C→B costs 1. No warning, no error — just a confidently wrong number. Negative weights show up whenever a leg of a route carries a credit: a regenerator that adds gain in an RF chain modeled in dB, an energy-recovery segment, a currency conversion in log space. If any edge can be negative, Dijkstra is disqualified, full stop.

Bellman–Ford gives up the greedy shortcut and simply sweeps every edge, relaxing where possible, V−1 times — enough rounds for a correct distance to propagate down the longest possible simple path. It costs O(V·E) but handles negative edges correctly, and it comes with a built-in alarm: if a V-th sweep still finds an edge to relax, the graph contains a negative cycle and "shortest path" is undefined — you can loop forever driving the cost to −∞. In a currency graph that alarm has a name: arbitrage. Bellman–Ford also decomposes naturally into a distributed algorithm — each node needs only its neighbors' current tables — which is why it, not Dijkstra, powered early packet routing ^[6]^[10]. The cost of that decentralization is slow convergence and the count-to-infinity pathology, where bad news about a dead link ratchets through the network one increment per exchange.

A* is Dijkstra with a compass. Adding h(n) to the priority biases the search toward the goal, and the guarantee survives under one condition: the heuristic must be admissible — it never overestimates the true remaining cost ^[7]. Set h = 0 everywhere and A* collapses to exact Dijkstra; make h aggressive but occasionally over the truth and the search gets faster while silently surrendering optimality. That trade is made deliberately in games and accidentally in engineering tools. A consistent heuristic (satisfying the triangle inequality along edges) buys the further guarantee that no node is expanded twice.

The subtler modeling mistakes outrank the algorithmic ones:

Costs that don't add. Shortest-path machinery assumes path cost is the sum of edge weights. Link reliability multiplies along a path — take −log of each edge first, then sums work. Bottleneck bandwidth is the minimum along a path, not the sum — that's a widest-path problem, and feeding it to Dijkstra unmodified answers a question nobody asked.
Optimizing the wrong weight. The algorithm returns the optimum of whatever you encoded. A routing metric of hop count will happily send traffic over one long satellite hop instead of three fast fiber hops. Garbage weights, optimal garbage.
Re-solving from scratch. Asking for all-pairs distances by running Dijkstra V times is legitimate; not noticing that the graph hasn't changed since the last run is not. Conversely, caching routes across a topology change is how test networks end up black-holing packets.

History

The problem came out of 1950s operations research, and the algorithm now called Bellman–Ford was found at least three times independently. Alfonso Shimbel described the relaxation method in 1955 in work on communication nets; Lester Ford Jr. wrote it up in a 1956 RAND Corporation note on network flow theory; Richard Bellman published "On a routing problem" in 1958, framing it through his dynamic programming; Edward Moore's version appeared in 1959 ^[4]^[5]^[6]. The name credits two of at least four discoverers — a routing problem of its own.

Dijkstra's story is the better one, because he told it himself. In 1956, a 26-year-old programmer at the Mathematisch Centrum in Amsterdam needed a demonstration problem to show off the new ARMAC computer. Sitting on a café terrace with his fiancée after a morning of shopping, he worked out the algorithm in his head — by his own account in about twenty minutes, without pencil or paper ^[1]^[2]. The demo computed shortest routes between 64 Dutch cities, 64 chosen so a city number would fit in six bits ^[1]^[3]. He didn't consider it publishable until an editor asked; the short paper, "A Note on Two Problems in Connexion with Graphs," finally appeared in 1959 ^[1]^[3]. It remains, per operation, one of the highest-value café stops in engineering history.

A* arrived in 1968 from Peter Hart, Nils Nilsson, and Bertram Raphael at Stanford Research Institute, who needed Shakey — the first mobile robot that planned its own actions — to find efficient paths through its world, and proved their heuristic search both correct and minimal in the computation it performs ^[7]^[8]. Fifty years later their algorithm routes characters through video games, robots through warehouses, and cars through your Friday commute.

Related tools

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →