The Simple, Elegant Algorithm That Makes Google Maps Possible

Michael Byrne in Motherboard:

Algorithms are a science of cleverness. A natural manifestation of logical reasoning—​mathematical induction, in particular—a good algorithm is like a fleeting, damning snapshot into the very soul of a problem. A jungle of properties and relationships becomes a simple recurrence relation, a single-line recursive step producing boundless chaos and complexity. And to see through deep complexity, it takes cleverness.

It was the programming pioneer Edsger W. Dijkstra that really figured this out, and his namesake algorithm remains one of the cleverest things in computer science. A relentless advocate of simplicity and elegance in mathematics, he more or less believed that every complicated problem had an accessible ground floor, a way in, and math was a tool to find it and exploit it.

In 1956, Dijkstra was working on the ARMAC, a parallel computing machine based at the Netherlands’ Mathematical Center. It was a successor to the ARRA and ARRA II machines, which had been essentially the country’s first computers. His job was programming the thing, and once ARMAC was ready for its first public unveiling—after two years of concerted effort—Dijkstra needed a problem to solve.

“For a demonstration for noncomputing people you have to have a problem statement that non-mathematicians can understand,” Dijkstra recalled in an interviewnot 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.”

More here.