You type two addresses into a navigation app. Within a fraction of a second, it returns a route. Not an approximate one. The shortest one, accounting for real road constraints, distances, and travel times.
The road network it searched could span an entire continent. The graph underlying Europe's road network alone has hundreds of millions of nodes and edges. So how does the system search it so quickly?
The answer isn't one clever algorithm. It's a progression of improvements, each one shifting more work from query time to preprocessing, until the actual online search becomes almost trivially small.
The Graph Underneath
A road network maps naturally onto a weighted directed graph. Intersections become nodes. Roads become edges. Travel time or distance becomes the edge weight. Finding the fastest route between two places becomes finding the minimum-cost path between two nodes.
