Even before the advent of Google Maps, folks were using programs like MapQuest to print up directions and figure out the shortest route between any two locations. While it’s easy to take mapping apps for granted these days, there’s some interesting mathematical algorithms at work behind the scenes that make it all possible.
Not many people are aware of this, but the computer algorithm that makes mapping programs so convenient dates all the way back to 1956, when a programmer named Edsger W. Dijkstra needed to come up with a solvable problem as a means to showcase the power of a new ARMAC computer. Dijkstra himself is a bit of a computing legend, having received the Turing Award in 1972.
Related: Free Gmail plugin lets you see if your emails are being tracked before you open them
Seeking to come up with a relatable problem, Dijikstra settled on “the shortest way to travel from Rotterdam to Groningen.”
“For a demonstration for noncomputing people you have to have a problem statement that non-mathematicians can understand,” Dijkstra recalled in an interview not long before his 2002 death. “They even have to understand the answer. So I designed a program that would find the shortest route between two cities in the Netherlands, using a somewhat reduced road-map of the Netherlands, on which I had selected 64 cities.”
The algorithm underpinning Dijikstra’s work, and indeed, the basic mapping functionality in many programs, was something he said he came up with while casually drinking coffee. The algorithm itself was highlighted in a published paper from 1959 and is appropriately called Dijkstra’s algorithm.
Notably, Dijkstra’s algorithm has applications beyond traditional navigation. It’s also been used for things like urban planning, network routing protocols, and optimal chip design.
