Designing a Map Routing System

A routing system finds the fastest or shortest path between two geographic points.

Road Graph

Roads modeled as directed weighted graph:

Nodes: Intersections (lat, lng)
Edges: Road segments (speed limit, distance, direction)

Weight: travel_time = distance / speed

Dijkstra's Algorithm

Finds shortest path from source to all nodes.

def dijkstra(graph, start, end):
  dist = {start: 0}
  pq = [(0, start)]  # (distance, node)

  while pq:
    d, u = heappop(pq)
    if u == end: return dist[end]

    for v, weight in graph[u].neighbors:
      if dist[u] + weight < dist.get(v, inf):
        dist[v] = dist[u] + weight
        heappush(pq, (dist[v], v))

Time complexity: O((V + E) log V)

A* Algorithm

Dijkstra with heuristic — explores promising directions first.

f(n) = g(n) + h(n)
g(n) = cost from start to n
h(n) = estimated cost from n to end (Haversine distance)

Result: 10-100x faster than Dijkstra for point-to-point

Graph Partitioning

Planet-sized graph (5B nodes) can't fit in one machine:

Hierarchical Highway Decomposition:
  Level 1: Local roads
  Level 2: City roads
  Level 3: Highways

Contraction Hierarchies: Precompute shortcut edges
→ 1000x faster routing for long distances

Real-Time Traffic

Sources: GPS probes from drivers, sensor data, incidents
    ↓
Edge weight = base_time × traffic_factor
    ↓
A* routing uses current weights

ETA Prediction

ML model inputs:
  - Route distance
  - Time of day
  - Day of week
  - Current traffic
  - Historical patterns

Output: ETA with confidence interval
"17 min (usually 15-22 min)"

Conclusion

A* with Contraction Hierarchies handles planet-scale routing in milliseconds. Real-time traffic edge weights and ML-based ETA make routes practically accurate.