How graph routing finds the shortest path.

Graph routing finds the shortest (or cheapest) path between two vertices in a weighted graph. The four classical algorithms — Dijkstra (1959), A* (Hart, Nilsson & Raphael, 1968), Bellman-Ford (1956-58), Floyd-Warshall (1962) — solve the same problem with different trade-offs around negative edges, heuristics, and all-pairs vs single-source.

You have a graph: vertices and edges, edges weighted with non-negative cost. You have a start vertex and a goal vertex. You want the path between them with minimum total cost. This is the shortest-path problem, and it shows up everywhere — routing protocols, navigation apps, network flow, dependency resolution.

Three classical algorithms solve it. Each handles a slightly different version of the problem and pays for its generality with extra work.

The grid below is a graph: each cell is a vertex, every cell is connected to its four neighbours with weight 1, walls are missing edges. Pick start and goal, draw walls, then run. Watch the difference between Dijkstra (expands radially) and A* (biases toward the goal).

Dijkstra maintains a priority queue (a min-heap) of vertices keyed by tentative distance from the start. The loop pops the cheapest unvisited vertex; for each neighbour, if the path through this vertex is cheaper than the neighbour's current best, update it. Repeat until the goal is popped. The algorithm dates to 1956 and has barely changed.

The greedy property is what works: by the time you pop a vertex, its distance is final. No later relaxation can shorten it because all unvisited vertices have at least its distance, and all edges are non-negative — adding a non-negative edge can never decrease the total. This is exactly why negative edges break Dijkstra.

A* is Dijkstra with a twist: the priority is g(n) + h(n), where g is the actual cost from start and h is a heuristic estimate of cost from n to goal. The heuristic biases the search toward the goal, expanding far fewer vertices.

For A* to find the optimal path, the heuristic must be admissible — never overestimate the actual remaining cost. On a grid with unit cost moves, Manhattan distance is admissible (it's the lower bound). Stronger property — consistent (monotonic) — guarantees no vertex needs reopening. Both are weak conditions; almost any reasonable distance estimate satisfies them.

If even one edge can be negative, Dijkstra fails — its greedy guarantee breaks. Bellman–Ford solves this by relaxing every edge V−1 times. After that many iterations, every shortest path is settled. One more iteration: if anything still relaxes, there's a negative cycle.

The price is O(V·E) — much slower than Dijkstra's O((V+E) log V) for typical graphs. Bellman–Ford is the right answer when (a) the graph has negative weights, or (b) you need negative-cycle detection (financial arbitrage, currency conversion, distance-vector routing protocols like the kind BGP grew out of).

Sometimes you need shortest paths between every pair of vertices, not just one source. Running Dijkstra from every vertex is one approach (V × O(E log V)). The alternative — Floyd–Warshall — uses dynamic programming to do all pairs in O(V³).

For dense graphs (E close to V²), Floyd–Warshall wins. For sparse graphs (E close to V), repeated Dijkstra wins. Floyd–Warshall also handles negative edges and detects negative cycles. It is one of the shortest, prettiest algorithms in the literature — three nested loops.

Negative weights? Bellman–Ford. Need a goal-biased search and a usable heuristic? A*. Otherwise, single-source non-negative? Dijkstra. All-pairs on a small dense graph? Floyd–Warshall.

Every other shortest-path algorithm in the wild — Yen's, contraction hierarchies, ALT, transit-node routing — is one of these four with engineering layered on top. Knowing the four primitives is more than enough to read any production routing code.

Google Maps / Apple Maps / OSRM

Real road graphs are billions of nodes; vanilla Dijkstra is too slow. Production uses contraction hierarchies (Geisberger et al., 2008) — a precomputed shortcut graph that answers point-to-point queries in milliseconds. OSRM ships an open implementation; Google's internal version is custom.

OSPF / IS-IS · interior routing

Inside an autonomous system, every router runs Dijkstra over the link-state database every few seconds. Convergence times: ~1-3 seconds for OSPF in a typical enterprise; sub-second with BFD-driven failure detection.

Uber dispatch

Match riders to drivers via shortest-path on a road graph + time-of-day traffic estimates. Uber's H3 hexagonal grid system reduces graph size for citywide computations. Public engineering blog (2018).

UPS / FedEx / DHL package routing

Vehicle Routing Problem (VRP) — generalises shortest path to multi-stop tours with capacity constraints. Solved via specialised heuristics (Clarke-Wright savings) plus shortest-path subroutines. UPS ORION saved ~$300M/year by reducing routes ~10%.

Network packet forwarding

Internet routers store FIBs (Forwarding Information Bases) computed from routing-table shortest paths; lookup uses tries (longest-prefix match) at line rate. The path computation runs on the route processor; the data plane just looks up.