OSPF, your GPS, and your service mesh routing are all Dijkstra's algorithm on different graphs.
Every time you load a web page, your request travels through a series of routers. Each router decides where to forward the packet. It does not consult a global map of the internet. It consults a routing table — a local summary of the best-known paths — and forwards the packet to the next hop.
How does the router build that table? By running Dijkstra's algorithm on its view of the network. The edges are links between routers. The weights are link costs. The output is a shortest path tree rooted at the local router.
This article traces one algorithm across three production systems. The graph changes. The edge semantics change. The algorithm does not.
Level 1 — The algorithm root
Dijkstra's algorithm solves the single-source shortest path problem. Given a weighted graph with non-negative edge weights and a source node, find the shortest path from the source to every other node.
The mechanics are compact. Set dist[source] = 0 and every other distance to infinity. Repeatedly extract the node with minimum dist[u]. For each neighbour v of u, relax the edge: if dist[u] + weight(u,v) < dist[v], update dist[v]. Continue until all nodes are extracted.
The greedy choice is correct because edge weights are non-negative. Once a node is extracted, its distance cannot decrease. Time complexity is O((V + E) log V) with a min-heap.
The algorithm does not handle negative weights. For those, use Bellman-Ford at O(VE). For dense graphs, use a matrix approach. For very large sparse graphs, use bidirectional Dijkstra or A* with a heuristic.
Level 2 — Routing protocols: OSPF
OSPF (Open Shortest Path First) runs inside most enterprise and data centre networks. It is a link-state protocol. Each router knows the complete topology of its area — every router, every link — and computes shortest paths independently.
Routers exchange Link State Advertisements (LSAs). An LSA announces a router's directly connected links and their costs. Each router maintains a Link State Database (LSDB) built from received LSAs. When the LSDB changes — a link goes up or down — every router reruns Dijkstra's on the updated graph and installs new shortest paths.
The tradeoff at this level is AT2 — Latency vs Throughput. OSPF recomputes SPF on every topology change. In a stable network this is cheap. In an unstable network with links flapping, SPF computation consumes significant CPU. OSPF uses SPF throttling — a configurable delay between successive computations — to survive instability. Throttling trades briefly stale routing tables for reduced CPU load.
The failure mode is FM4 — Data Consistency Failure. OSPF requires every router in an area to hold a consistent LSDB. During convergence — the window after a topology change when LSAs are still propagating — different routers hold different views of the network. Packets forwarded during this window may take suboptimal paths or form routing loops. OSPF convergence takes 1–5 seconds for modern implementations. Traffic can be disrupted during that window.
Large networks with hundreds of routers may take hundreds of milliseconds of CPU just for the SPF computation after a major change.
Level 3 — GPS navigation: Dijkstra with A*
A GPS navigator routes on a road network graph. Nodes are intersections. Edges are road segments weighted by travel time. The graph has millions of nodes. Standard Dijkstra at O((V+E) log V) is too slow for interactive use at that scale.
A* accelerates Dijkstra by adding a heuristic — an estimate of the remaining distance from any node to the destination. The heuristic steers the search toward the destination rather than expanding uniformly in all directions.
The heuristic must be admissible. An admissible heuristic never overestimates the actual remaining distance. For road networks, straight-line Euclidean distance to the destination is admissible. Roads are never shorter than a straight line. The heuristic is also usually close to the true remaining distance, so it prunes aggressively.
The tradeoff at this level is AT6 — Generality vs Specialization. Standard Dijkstra is general. It works on any graph with non-negative weights. A* is specialised. It requires a domain-specific admissible heuristic. When the domain provides one, A* expands an order of magnitude fewer nodes than Dijkstra on the same graph. When no good heuristic exists, A* degenerates to Dijkstra.
The specialisation is worth the implementation cost when the domain hands you a heuristic. Geographic coordinates on a road network do exactly that.
Level 4 — Service mesh routing: latency-weighted shortest path
A service mesh — Envoy, Istio, Linkerd — routes requests between services in a microservices architecture. Each service has multiple instances across multiple availability zones. The routing decision must minimise total request latency.
The service mesh is a weighted graph. Services are nodes. Edges are request paths between them. Weights are measured end-to-end latency — a running average or P99 over recent requests. Shortest-path computation on this graph determines routing.
What changes here is the edge semantic. In OSPF, link cost is a configured constant. In a service mesh, latency changes continuously as the system operates. A slow downstream service raises the weight on every edge to it. The router should immediately prefer alternate paths.
This forces the routing graph to be updated in near real-time from observability data. It also forces the shortest-path computation to rerun frequently or on change.
The failure mode that appears at this level is FM5 — Latency Amplification. The routing decision is made on measured latency. Measurements themselves take time to collect and propagate. If the measurement window is long, the router routes on stale weights and packets travel through a path that is no longer optimal. If the recomputation cadence is slow, every request during the stale interval pays the difference. Small measurement lags multiply across every hop in a multi-service request path.
Level 5 — What Dijkstra does not give you
Two production failure modes are not solved by the algorithm itself.
The first is FM6 — Hotspotting. Shortest path algorithms find paths by minimum cost. They do not balance load across equivalent paths. When two paths have equal cost to the same destination, Dijkstra picks one arbitrarily. Load concentrates on the selected path while the equivalent path sits idle.
Equal-Cost Multi-Path (ECMP) routing addresses this. ECMP explicitly load-balances across every equal-cost path — a post-processing step that standard Dijkstra does not provide. If the graph has redundant paths and load matters, add ECMP.
The second is inter-domain routing. BGP (Border Gateway Protocol) routes between organisations on the internet — AWS, Google, Cloudflare, your ISP. BGP is not a shortest-path protocol. It uses policy-based path selection: AS path length, local preference, community attributes. Dijkstra owns intra-area routing. Policy owns inter-domain routing. Do not confuse the two.
Kubernetes load balancing sits between these. Current kube-proxy implementations use round-robin or random selection. Advanced service meshes incorporate real-time latency measurements into routing decisions. Latency-weighted routing is an active area of development, not a solved problem.
What this means for your system right now
Every routing decision is a version of AT4 — Precomputation vs On-Demand. You are choosing to precompute a routing table so packet forwarding is a table lookup, not a graph search. The precomputation cost is paid on topology change. The lookup cost is paid on every packet.
The questions that determine whether the design is correct are always the same.
How stable is the graph? OSPF assumes topology changes are rare. If your links flap constantly, SPF throttling is not optional. If your service latencies fluctuate every second, the recomputation cadence itself becomes a bottleneck.
How long is the convergence window? During convergence, routers hold inconsistent views. Packets can loop. Whether 1–5 seconds of possible disruption is acceptable depends on what the packets carry.
Do you have a good heuristic? If yes, use A*. If no, do not manufacture one — an inadmissible heuristic produces wrong answers, not slower answers. Standard Dijkstra is the safe default.
Are equal-cost paths going to waste? If shortest-path routing concentrates load on one of several equivalent paths, add ECMP. The algorithm will not do it for you.
The signal that tells you this applies to your system
You are routing requests through a weighted graph from source to destination. The path that minimises total cost — latency, hops, money — is not obvious by inspection. Apply Dijkstra, or A* when the domain hands you an admissible heuristic. When the graph has equal-cost paths and load matters, add ECMP on top.
If your routing weights change continuously — because they come from live measurements — the harder question is not which algorithm. The harder question is how often you can afford to rerun it before staleness costs you more than recomputation does.
The full framework treatment — compression blocks, three-level exercises, and the complete AT/FM mapping — is in Book 2: Algorithm Engineering, Chapter 7 (Shortest Path in Practice). Free chapter available at computingseries.com/books/book2.