Shortest Paths

Every time your phone says "fastest route, 23 minutes," it has just solved a shortest-path problem on a graph with millions of edges. The roads are edges, the intersections vertices, and each edge carries a weight — its travel time. Out of astronomically many possible routes, the algorithm finds the cheapest one in a fraction of a second. The idea behind it is elegant enough to explain in a single sentence.