Back in the hazy olden days of the pre-2000s, navigating between two locations generally required someone to whip out a paper map and painstakingly figure out the most optimal route between those depending on the chosen methods of transport. For today’s generations no such contrivances are required, with technology having obliterated even the a need to splurge good money on a GPS navigation device and annual map updates.

These days, you get out a computing device, open Google Maps or equivalent, ask it how you should travel somewhere, and most of the time the provided route will be the correct one, including the fine details such as train platform and departure times. Yet how does all of this seemingly magical route planning technology work? It’s often assumed that Dijkstra’s algorithm, or the A* graph traversal algorithm is used, but the reality is that although these pure graph theory algorithms are decidedly influential, they cannot be applied verbatim to the reality of graph traversal between destinations in the physical world.

Continue reading “Where Graph Theory Meets The Road: The Algorithms Behind Route Planning” →