Dijkstra Algorithm: Key to Finding the Shortest Path, Google Map to Waze
How does Google Maps find the directions?
These popular rideshare apps including Uber and Lyft use Waze, which was bought by Google Maps back in 2013 for a little over a billion dollars. Personally, I use Waze for driving and Google Maps when I’m not.
How do you find the shortest path ?
There are three major shortest path algorithms: Bellman Ford’s Algorithm, Dijkstra’s Algorithm, and Floyd–Warshall’s Algorithm.
Google Map is based on this algorithm, Dijkstra’s Algorithm which was invented by Edsger W. Dijkstra, Dutch essayist DescriptionEdsger Wybe Dijkstra was a Dutch systems scientist, programmer, software engineer, science essayist, and pioneer in computing science. A theoretical physicist by training, he worked as a programmer at the Mathematisch Centrum from 1952 to 1962.
Dijkstra is a greedy algorithm. What is greedy algorithm?
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solution are best fit for Greedy.
A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem. Greedy algorithms are quite successful in some problems, such as Huffman encoding which is used to compress data, or Dijkstra’s algorithm, which is used to find the shortest path through a graph.
However, in many problems, a greedy strategy does not produce an optimal solution. For example, in the animation below, the greedy algorithm seeks to find the path with the largest sum. It does this by selecting the largest available number at each step. The greedy algorithm fails to find the largest sum, however, because it makes decisions based only on the information it has at any one step, without regard to the overall problem.
With a goal of reaching the largest sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step and will not reach the best solution, which contains 99.
Dijkstra’s algorithm (or Dijkstra’s Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants; Dijkstra’s original variant found the shortest path between two nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.
- => => → find the shortest path (minimum cost path)
Work Cited
https://www.myrouteonline.com/blog/what-is-the-best-shortest-path-algorithm
http://math.mit.edu/~rothvoss/18.304.3PM/Presentations/1-Melissa.pdf
https://brilliant.org/wiki/dijkstras-short-path-finder/
https://medium.com/basecs/finding-the-shortest-path-with-a-little-help-from-dijkstra-613149fbdc8e
https://www.hackerearth.com/practice/notes/dijkstras-algorithm/
https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/
https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/dijkstra
https://rubygarage.org/blog/how-to-make-a-gps-app-like-waze
https://www.quora.com/What-routing-algorithm-does-Waze-use
https://wiki.waze.com/wiki/Routing_server#Routing_algorithm_refinements
