The famous algorithm that made navigation in Google Maps a reality

Dijkstra at the blackboard during a conference at ETH Zurich in 1994 - Wikipedia

Dijkstra: The man who made digital navigation a reality. Copyright: Andreas F. Borchert Wikipedia

Google Maps is arguably one of the most famous Geospatial applications ever.  Overnight, it transformed the way we navigate and made it mainstream to use a digital map to get from Point A to Point B.

Before Google Maps came along, most people were still using paper maps to navigate and then we quickly adapted and  started using Digital maps. Google maps wasn’t the first one to have these features but it certainly did help make navigation mainstream.

Digital maps had several advantages over the print equivalent – different zoom levels, ability to add your own points of interest, etc but perhaps the most attractive feature was the ability to use the computer (or smartphone) to calculate the shortest distance from point A to B without needing to figure it out yourself or asking someone who has lived in the place long enough to know it by experience.

Just how important was navigation to the success of digital maps? Perhaps, a lot! We all use digital maps today and more often than not, its for navigation.

The Simple algorithm that made Navigation possible

Dr. Dana Tomlin‘s work in the early 80’s titled “Map Algebra” paved the way for GIS to become a powerful application that it is today. Similarly, it was Edsger W. Dijkstra’s work on the shortest path algorithm that eventually was named after him – the Dijkstra’s algorithm that made Navigation possible.

Dijkstra Algorithm - Wikipedia

Dijkstra Algorithm – Wikipedia

The core of this algorithm is what powers the navigate functionality at Google Maps, Apple Maps, Here, OpenStreetMap and any other digital map that you probably use. Yes, its not exactly the same algorithm that powers navigation application today but A* search and other algorithms are an extension of the original Dijkstra’s algorithm.

We are so used to navigation using digital maps that we no longer think about how complex this task could be, if not for Dijkstra’s algorithm that solved the shortest path problem in most efficient manner possible. The fact that the algorithm is still being used 50+ years after it was published speaks volumes about it.

Thank you, Edsger W. Dijkstra 🙂
Say thanks for this article (2)
The community is supported by:
Become a sponsor
Geo Addressing Decoded Part 1: Why Does Geo Addressing Matter?
Aleks Buczkowski 04.16.2024
#Business #Featured
The Earth Observation Hub Report: 2024 Industry Trends and Analysis
Avatar for Muthukumar Kumar
Muthukumar Kumar 03.13.2024
#Business #Featured #GeoDev
Geo Addressing Decoded Part 2: Beyond Coordinates – Exploring the Depth and Impact of Geo Addressing
Aleks Buczkowski 05.2.2024
Next article
#Featured #Ideas

Submarine Cable Map is one of the best maps of 2015


Every year TeleGeography – a telecom data research firm, releases a stunning map related to global communications. This year’s map shows global submarine internet cables. We are not aware of it but 99% of all international data is transmitted via this under water network. Without them, the world as we know wouldn’t exist.

It is a beautiful map. It pays tribute to the pioneering mapmakers of the Age of Discovery, incorporating elements of medieval and renaissance cartography. At that time maps were works of art, decorated with illustrations. Their aesthetics was as much important as their functional qualities. In the corners of the map you can also find information about “latency” (how long it takes for information to transmit) and “lit capacity” (which shows how much traffic a system can send, usually measured in terabytes) between continents.

TeleGeography released also zoomable version of their map, which you can view here.

Read on