The Simple, Elegant Algorithm That Makes Google Maps Possible

Motherboard has a great piece on the math behind Google maps.

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 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.”

“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.

The result of such an explosion is that problems, like shortest path problems, grow so quickly as to become practically incomputable, taking a practically infinite amount of time to solve. It only takes a handful of nodes in a given map or graph for the number of possible combinations to push into the billions, requiring vast and unreasonable amounts of time.

The easiest way to explain Dijkstra’s algorithm is probably with an example. Take the graph below, where the numbers given are the weights of each connection. (A weight could be a simple distance or really any relative cost associated with traversing a particular connection that we’re seeking to minimize.) To start, we assign s, our starting position, the value 0. It takes 0 miles (or whatever) to get here because it’s the beginning position. Next, we look at the neighboring nodes of s, which we can imagine as a sort of frontier to be explored.

Read the full article here.


Have an amazing project to share? The Electronics Show and Tell is every Wednesday at 7:30pm ET! To join, head over to YouTube and check out the show’s live chat and our Discord!

Join us every Wednesday night at 8pm ET for Ask an Engineer!

Join over 38,000+ makers on Adafruit’s Discord channels and be part of the community! http://adafru.it/discord

CircuitPython – The easiest way to program microcontrollers – CircuitPython.org


New Products – Adafruit Industries – Makers, hackers, artists, designers and engineers! — New Products 11/15/2024 Featuring Adafruit bq25185 USB / DC / Solar Charger with 3.3V Buck Board! (Video)

Python for Microcontrollers – Adafruit Daily — Python on Microcontrollers Newsletter: A New Arduino MicroPython Package Manager, How-Tos and Much More! #CircuitPython #Python #micropython @ThePSF @Raspberry_Pi

EYE on NPI – Adafruit Daily — EYE on NPI Maxim’s Himalaya uSLIC Step-Down Power Module #EyeOnNPI @maximintegrated @digikey

Adafruit IoT Monthly — The 2024 Recap Issue!

Maker Business – Adafruit Daily — Apple to build another chip at TSMC Arizona

Electronics – Adafruit Daily — SMT Tip – Stop moving around!

Get the only spam-free daily newsletter about wearables, running a "maker business", electronic tips and more! Subscribe at AdafruitDaily.com !


No Comments

No comments yet.

Sorry, the comment form is closed at this time.