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 N...
