Route Finding & ETA Backbone

A rider taps a destination. Before a price appears, before a driver is assigned, before the countdown starts — the system has to know how long the trip will take on real roads. That answer comes from the routing layer: shortest-path queries over a city-scale graph, fired millions of times per minute across pricing, dispatch, and in-trip tracking.

This unit builds that ETA backbone — the road graph, classical search (Dijkstra, A*), goal-directed pruning (ALT), and production-speed preprocessing (Contraction Hierarchies + OSRM). You will implement each stage, self-check with python test.py, and unlock sub-units with deterministic checkpoint answers. Everything downstream in the Uber track — nearest-driver ranking, dispatch scoring, fare meters — assumes this layer is fast and correct.