Module 13: Network Analysis

13.2 Shortest Path Routing

Dijkstra, A*, and the algorithms behind every turn-by-turn route.

Lesson 65 of 100·15 min read

Key takeaways

Dijkstra's algorithm finds the shortest path from one node to all others in O((E + V) log V).

A* uses a heuristic to prune exploration — fast for point-to-point routing.

Contraction Hierarchies and similar techniques reduce long-distance routing to milliseconds.

Introduction

You've loaded a network graph. Now you want to answer "what's the fastest route from A to B?" This lesson covers the core algorithms that power everything from Uber's ETA to the routing plugin in QGIS.

Dijkstra's algorithm

Edsger Dijkstra's 1959 algorithm. Given a source node, finds shortest paths to all others. Pseudo-code:

Code

[object Object][object Object]

Complexity: O((E + V) log V) with a binary heap. Runs in seconds on a city-scale network.

Python:

Python

import networkx as nx

A*

Dijkstra explores outward in all directions. A* uses a heuristic to prioritise nodes likely on the path — typically the Euclidean or geodesic distance from the current node to the destination. Properly chosen heuristics make A* drastically faster while still guaranteeing the optimal path.

Python

1def heuristic(u, v):
2    return great_circle_distance(G.nodes[u]['x'], G.nodes[u]['y'],
3                                 G.nodes[v]['x'], G.nodes[v]['y'])

For most point-to-point routing, A* is the workhorse.

Bidirectional search

Run Dijkstra / A* from both endpoints simultaneously; they meet in the middle, cutting runtime roughly in half. Most production engines do this.

Contraction Hierarchies

Pre-processing step: repeatedly remove the least-important nodes from the graph, adding shortcuts to preserve distances. Result: a hierarchy where short-distance routing stays local and long-distance routing quickly jumps to high-level edges.

Preprocessing: expensive (hours for a continent).
Query time: milliseconds on a country-scale graph.
Used by: OSRM, GraphHopper, Valhalla (optional).

Turn costs

Real intersections slow you down even without stopping. Turn costs add penalties:

Straight: 0 s.
Right: 5 s.
Left: 10 s.
U-turn: 30 s.

Encoded via turn edges or penalty tables. Engines that don't support them produce too-optimistic ETAs.

Time-dependent routing

Traffic varies by time of day. Time-dependent Dijkstra uses different edge weights at different times:

Code

weight(edge, t) = edge.length / speed(edge, t)

Speed profiles (from historical traffic data) or real-time feeds produce hour-by-hour weights. Mapbox, HERE, Google route with these.

Turn-by-turn directions

From a route (a sequence of nodes), generate human-readable directions:

At each intersection, decide the turn angle.
Consult street names to phrase ("turn right onto Main Street").
Include distance to next turn.
Add landmarks where available.

Multi-destination

Routing to or from many destinations at once — distance matrices, isochrones, set-cover. Module 13.3 covers service areas and isochrones.

Alternatives

Beyond shortest:

Alternative routes — return top-3 routes, no more than X% longer.
Preference-aware — avoid tolls, favour scenic, prefer low elevation gain.
Safety-aware — for cycling, favour bike lanes.
Fuel-minimising — EVs want to minimise energy, not just distance.

Engines expose these via options.

Failures

No path — source and destination in different components.
No reachable node — source snapped to a private drive.
Unreasonable route — often a data quality issue (incorrect turn restriction or missing oneway).

Log failures with context; diagnose in the source data.

Self-check exercises

1. What guarantee does A* offer over Dijkstra?

A* is always at least as fast as Dijkstra given an admissible heuristic (one that never overestimates the true remaining cost) and produces the same optimal path. With a good heuristic like great-circle distance, A* explores a tiny fraction of the graph that Dijkstra would explore — often 10–100× faster for point-to-point routing.

2. Why do production routers use Contraction Hierarchies for continental routing?

Plain Dijkstra / A* on a 100 million-edge graph takes seconds per query — not acceptable for consumer apps with millions of requests/minute. CH preprocesses the graph into a hierarchy where queries touch only a few thousand edges, giving millisecond responses. The cost is preprocessing time (hours) and extra memory, but that's paid once.

3. Your ETA underestimates actual travel time by 20 %. What's likely missing?

Turn costs (intersections cost real seconds) and time-dependent speeds (rush-hour slowdowns). Also check whether you modelled signalised intersections, traffic calming, or historical traffic profiles. Another possibility: you used free-flow speed limits where actual average speeds are much lower.

Summary

Dijkstra is the foundational shortest-path algorithm.
A* adds a heuristic for practical speed.
Contraction Hierarchies scale to continents.
Turn costs and time-dependent speeds make ETAs realistic.