Google Maps Made Possible by an Elegant, Simple Algorythm

“What’s the shortest way to travel from Rotterdam to Groningen?,” Dijkstra said. “It is the algorithm for the shortest path, which I designed in about 20 minutes.”

Google Maps does this for us now and we don’t even really think about what a complex task it could be. Shortest path problems, a key feature of graph theory with a whole lot of pretty obvious real-world applications, get insanely deep very fast. The result is known (informally) as a combinatorial explosion, which is where the number of different combinations that must be explored in a given problem grows exponentially.