Hey, all! We all use apps and procure various services on an everyday basis, right? But did you ever think of the algorithm that it uses? Today, we will look at one of the most commonly used services, Google Maps, and understand the algorithm behind this.
So, what is Google Maps?
With more than a billion active users every month, Google Maps was launched in 2005 as a desktop solution to help people get from ‘ point A to point B ‘. It’s been a long run, and today, after more than 15 years, Maps has become this inevitable service that we all use on almost a daily basis.
Which algorithm do they use?
Google Maps essentially uses two Graph algorithms – Dijkstra’s algorithm and A* algorithm, to calculate the shortest distance from point A ( Source) to point B ( destination). A graph data structure is essentially a collection of nodes that are defined by edges and vertices.
If you have been into programming for quite a while now, you most probably would have heard of Dijkstra’s algorithm as well. Dijkstra’s algorithm is one of the greedy algorithms used to optimize and find the shortest path between nodes in a graph. Dijkstra’s algorithm is an effective algorithm proposed by Edsger.W. Dijkstra in the year 1956 and published three years later.
There exist many variants for this algorithm. The original algorithm found the shortest path between two nodes, whereas the variant fixes a single node as the source and then finds the shortest path to other nodes. And this is the concept that is implemented by Google Maps to calculate and show us the shortest path between two points. But there’s one fallback to this algorithm. The number of nodes in Google Maps is almost infinite or uncountable, and this algorithm may fail due to an increase in time and space complexity. And that’s where the A* algorithm proves useful.
A* graph algorithm is one of the best graph traversal and path search algorithms, formulated especially for weighted graphs. This algorithm is more preferred due to its completeness, optimality, and optimal efficiency. A* algorithm is similar to Dijkstra’s algorithm and uses a heuristic function to navigate a better and more efficient path. Unlike Dijkstra’s, the A* algorithm focuses on only the destination nodes and not the others; thus, this algorithm proves to be more proficient. It also takes parameters such as time requirement, distance, etc., optimizing and choosing the better nodes. So now, Google Maps also uses this algorithm to calculate the shortest path, owing to its high accuracy and ability to deal with huge chunks of data and mammoth graphs.
Well, that was enlightening, right?
So the next time you use Google Maps to reach a destination, you sure would remember the algorithm behind the app and how this path was chosen as the most optimum one for you.
Adios, mate. Until next time, keep reading mind-blowing articles, and learn how the apps work!