The famous algorithm that made navigation in Google Maps a reality

1
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 🙂
I am one of those passionate "Geo-geeks" and "Geo-people" who is just too excited about everything Geo and Management. Location information and spatial technologies are just too big to take a back seat and watch them revolutionize the world. Always curious and looking for ways to innovate, I guess that it comes naturally by the gene pool I inherited from an engineer Mom and a researcher Dad.