Rattibha

Nikki Siapno

9 Tweets 11 reads May 11, 2023

In less than 2 seconds, Google Maps can calculate the fastest path.
But how?
Give me 3 minutes and I’ll show you:

Google is among the few companies that have nailed swift processing speeds and quality results.
Google Maps and Search are prime examples of that.
It's all thanks to sophisticated algorithms.
Here's an overview of the process behind Google Maps:

Under the hood, Google uses advanced routing algorithms.
Entire road networks are represented as a graph.
Each node is a destination; such as landmarks or addresses.
And each edge is a path between two destinations.
Attributes such as distance & speed are attached to an edge.

The values of these attributes are updated with real-time data.
From there, routing algorithms like Dijkstra's Algorithm and A* Search Algorithm searches for the optimal path by doing the following:

Firstly, the source and destination nodes are identified.
Next, the algorithm uses the attributes on each relevant edge to calculate and find the shortest path.
How it does this depends on the specific algorithm used.

For example, Dijkstra's Algorithm starts at the source node and explores the unvisited nodes with the shortest known distance from the source.
It continues this process until it reaches the destination.

The A* search algorithm is very similar.
But instead, it uses a heuristic function to estimate the remaining distance to the destination from each point.
It uses this info to prioritize which node to travel to next, to ensure it doesn’t travel further away from the destination.

These algorithms are a great example of how to break down thorny problems into more manageable units.
The problem-solving and optimization techniques used by these algorithms can be applied to systems beyond navigation.

If this thread was helpful to you:
1. Connect with me: Linkedin.com for more content like this.
2. Follow linkedin.com for quality Programming & Tech content.
3. Like & Retweet the tweet below to share it with others👇