Well, for you to visit this page means you are really interested to know how to build your own google maps. However, we aren’t gonna do something that crazy here. We will be building an algorithm, though which will let us find the shortest path between any two locations. So let’s get started.
Problem at hand
You live in an era before google maps was made, so you need to rely on a printed map to get to your destination. However, you know how to code, so you try to build a google map on your own.
What you basically want to do is, you want to create something that tells you the shortest distance you need to travel from your current location to your destination, given all the different locations in the map.
Intuition
Let’s first try to analyse our options here. First, we can try out each of the paths and figure out which would give you the minimum distance. However, this is very inefficient. Consider you have N locations on the map. You will have n(n-1) paths connecting each of the two locations and to find the minimum by considering each combination of these n(n-1) paths is far too inefficient.
Now, let’s try to see this from a different perspective. You consider each location as a vertex and the path joining any two locations, an edge between the vertices. You end up constructing a graph in this way. Now, all you need to do is find the shortest distance of the path that will let you reach the destination. Does this sound familiar to some algorithm you already know ? If not, then let’s see how we achieve this. Just FYI, this is called Dijkstra’s Algorithm (yeah I didn’t make it so no credits to me for the algorithm as much as I wanted to take it all for myself)
Solution
Here, we perform an algorithm similar to bfs (if you don’t know what that is, I’d highly recommend you to check it out from here). We take a priority queue (min heap) instead of a queue.
We maintain a distances array which stores the minimum distances of all nodes from the source. Initially, we make the distance of source as 0 and insert a pair of 0 and source node in the queue. Now, we iterate until the priority queue is empty and in each iteration, we store the min between the distance of the child node and the sum of distanced of the parent and edge weight of the child in the distance of the child. Once this is done, we add the pair of distance and child node to the priority queue if the sum is more than the previous distance.
Once the loop is over, we will get all the minimum distances in the distance array.
Now that you’ve thought of this algorithm, the next question that would come to you mind is, how efficient is this ? So let’s try to answer that.
Here, we are traversing through the entire graph and we visit each node exactly once. So, the time complexity will be O(N+E)
Also, we are using a priority queue, so the space complexity is O(N)
As you can imagine, it’s pretty efficient as compared the the naive way that came you us at the beginning (i.e., to check for each combination of the path and compute the minimum distance).
Well, with that, you’ve successfully planned the algorithm to build the google maps. What are you waiting for ? Go and build it so that u can give it to your friends and amaze them with your genuis.
Thanks for reading it till the end and stay tuned for more amazing content like this one!
Top comments (0)