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.

Adafruit publishes a wide range of writing and video content, including interviews and reporting on the maker market and the wider technology world. Our standards page is intended as a guide to best practices that Adafruit uses, as well as an outline of the ethical standards Adafruit aspires to. While Adafruit is not an independent journalistic institution, Adafruit strives to be a fair, informative, and positive voice within the community – check it out here: adafruit.com/editorialstandards

Stop breadboarding and soldering – start making immediately! Adafruit’s Circuit Playground is jam-packed with LEDs, sensors, buttons, alligator clip pads and more. Build projects with Circuit Playground in a few minutes with the drag-and-drop MakeCode programming site, learn computer science using the CS Discoveries class on code.org, jump into CircuitPython to learn Python and hardware together, TinyGO, or even use the Arduino IDE. Circuit Playground Express is the newest and best Circuit Playground board, with support for CircuitPython, MakeCode, and Arduino. It has a powerful processor, 10 NeoPixels, mini speaker, InfraRed receive and transmit, two buttons, a switch, 14 alligator clip pads, and lots of sensors: capacitive touch, IR proximity, temperature, light, motion and sound. A whole wide world of electronics and coding is waiting for you, and it fits in the palm of your hand.

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 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! — JP’s Product Pick of the Week 9/17/24 USB C Plug Breakout @adafruit @johnedgarpark #adafruit #newproductpick

Python for Microcontrollers – Adafruit Daily — Python on Microcontrollers Newsletter: CircuitPython Comes to the ESP32-P4, Emulating Arm on RISC-V, 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 — IoT Vulnerability Disclosure, Decorative Dorm Lights, and more!

Maker Business – Adafruit Daily — A look at Boeing’s supply chain and manufacturing process