How Google Map works and Dijkstra’s Algorithm

 We are all confided in our houses and this is the perfect time to analyze the tool which we use for our daily commute, Google Maps.

If you open the app now and see your general route, from Home to Work or Home to School , the travel time will be significantly less than the usual. Well this was expected right? Less traffic , clear road.

But the way it measures the “traffic” is more interesting.

The Shortest Route Problem

Observe this maze below.

Computer can solve this problem easily by brute-force method. (i.e trying to connect S and F by trying all possible routes), But there are more than one solution to this problem.

Now the question arises, how to reach from S to F as early as possible.

Travel time doesn’t depend on Start or Finish points but the route chosen, So here we look at Orange route and specifically a part of the orange route.

This part of the route has 3 properties. A(Starting point), B(End point) and K (some constant). 

The Constant K

Now imagine you are on a straight road, you have to reach from one end of that road to other. Depending your speed is constant. What factors would determine the travel time.

Generally there are 2 factors, i) length of road

                                               ii)  Roughness or Obstacles in the road.

Now you may guess where we are going (no pun intended ).

We define “K” value for  each part of the route and sum it up. After doing that we have K_orange  and K_blue .

 

 

Therefore now we compare and K_blue and K_orange , Which ever is low that path is the shortest.

In google maps, the value of K is variable and depends on the traffic and roughness of the road.

The traffic is measured by number of active android devices in that area. Sattelite detects mobiles and their, if it detects a good amount of devices in stationary on that road, the K value for that route shoots up and it suggests you to take an alternate route.

The other 2 routes may seem to be a faster route to the empire state building but as you can see thats not true.

and K values for Red marked road is higher than the one marked with blue, and this is constantly being updated in real time. 

Djikstra’s algorithm is not only by google maps but a lot of many services out there.

*lol*I myself tried to make an app for metro system in Delhi but I found Android Development too much cumbersome.