Graph & Routing

When you open Google Maps and ask for directions from New York to San Francisco, the server doesn't "look" at a map. To a computer, a map is strictly a mathematical construct called a Graph. Intersections are Nodes (or Vertices), and the roads connecting them are Edges. Each Edge has a Weight—a number representing the cost to travel that road, usually expressed in seconds. The routing problem is simply finding the mathematical sequence of Edges that yields the lowest total Weight.

Part 1: The Anatomy of a Road Network

Before algorithms can run, the physical world must be digitized into a data structure. Map providers (like OpenStreetMap) store spatial data. In memory, a routing engine typically represents this using an Adjacency List.

Instead of an unscalable 2D matrix (which would require trillions of empty cells for landmasses without roads), an Adjacency List is a HashMap where the Key is a Node ID, and the Value is an array of directly connected neighboring Nodes and their traversal costs.

Because traffic changes dynamically, "cost" is not a static physical distance. A 1-mile stretch of empty highway might have a cost of 60 (seconds), while a 0.2-mile stretch of gridlocked city center might have a cost of 400. Routing engines constantly update these Edge Weights in real-time based on live telemetry data from millions of smartphones.

Part 2: Dijkstra's Algorithm (The Expanding Puddle)

Invented by Edsger W. Dijkstra in 1956, this algorithm mathematically guarantees the absolute shortest path.

Dijkstra operates using a Min-Priority Queue (often implemented as a Binary Heap). The algorithm maintains a list of the shortest known distance from the Start Node to every other Node. Initially, Start is 0, and all others are Infinity.

• Pop the Node with the lowest current distance from the Priority Queue (The "Current Node").
• Iterate through all of its connecting Edges (Neighbors).
• Calculate the distance: Distance to Current Node + Edge Weight.
• If this calculated distance is strictly less than the neighbor's currently known shortest distance, mathematically overwrite it, and push the Neighbor into the Priority Queue.
• Repeat until the Destination Node is popped from the queue.

The Critical Flaw: Dijkstra is an "Uninformed" search. It has absolutely no concept of physical direction. If your destination is East, Dijkstra will indiscriminately explore roads going North, South, and West with equal fervor, expanding outward like a symmetrical puddle of water. On a massive graph (like the US road network with 20 million nodes), Dijkstra is catastrophically slow.

Part 3: A* (A-Star) and The Power of Heuristics

To fix Dijkstra's blind expansion, engineers use the A* (A-Star) Search Algorithm. A* introduces a psychological "magnet" called a Heuristic.

Instead of picking the next node based purely on how far it is from the start, A* scores nodes using the formula: f(n) = g(n) + h(n).

• g(n): The exact, known cost from the Start to the current node (Dijkstra's metric).
• h(n): The Heuristic—an algorithmic estimate of the cost from the current node to the Destination.

In geographic routing, h(n) is usually the Euclidean Distance (the straight-line "as the crow flies" distance) or the Haversine Distance (accounting for Earth's curvature).

Because the Priority Queue now sorts by f(n), A* heavily penalizes roads that physically move away from the destination coordinates. It actively prioritizes roads that geometrically point toward the goal. The puddle of water transforms into a laser-focused tendril aggressively seeking the target, exploring thousands of fewer nodes than Dijkstra.

Part 4: Contraction Hierarchies (Google Maps Scale)

A* is brilliant, but still too slow for a planet-scale request (like Seattle to Miami) requiring milliseconds of latency. Modern routing engines use Contraction Hierarchies (CH) to pre-process the graph.

A Contraction Hierarchy observes that you rarely take local residential roads for a cross-country trip. CH systematically permanently removes "unimportant" nodes (like dead-end neighborhood streets) from the in-memory graph, replacing them with "Shortcut Edges" that directly connect major highways.

When you request a route, the algorithm performs a Bidirectional Search: one search starts at the origin (moving "up" the hierarchy to local highways), and another starts at the destination (also moving "up"). They rapidly intersect on a major Interstate highway shortcut. This reduces a graph of 50 million nodes down to a few thousand critical junction checks, answering complex routing queries in under 5 milliseconds.

Conclusion: The Evolution of Search

Graph routing perfectly illustrates the evolution of computer science. We began with Dijkstra's brute-force mathematical certainty. We improved it with human-like spatial intuition (A* Heuristics). Finally, we conquered planetary scale by preemptively altering the dataset itself (Contraction Hierarchies), trading raw CPU cycles during search for massive upfront memory pre-computation.