Google Maps Shortest Path Algorithm: Fundamentals and Implementation

Get to implement the core logic using NetworkX and Graph-Tool

Contents

• Google-Maps
• Fundamentals of a Graph
• Dijkstra’s Algorithm
• Packages & Implementation
• Conclusion
• References
• Connect

Not all those who ‘use Google Maps’, are Lost! — Author

Google-Maps

Google Maps is a web mapping platform and consumer application offered by Google. It offers satellite imagery, aerial photography, street maps, 360° interactive panoramic views of streets (Street View), real-time traffic conditions, and route planning for traveling by foot, car, bike, air (in beta), and public transportation¹

One of the biggest reasons why Google Maps is popular is you can find the best and the shortest path from one specific location to another, despite you are driving, biking, walking, or using public transport, which eventually helps you to plan your route seamlessly.

To understand the algorithm behind one of the World’s Most Popular functionality we will have to dig into the fundamentals of Graph.

Graph

A graph is made up of Vertices (also called nodes or points) which are connected by Edges (also called links or lines). There are two common types of Graph :

• Undirected Graph
• Directed Graph

Mathematically, a Graph is an ordered pair G = (V, E) where :

• V is a set of vertices (also called nodes or points)
• E ⊆ {{x,y} | x,y ∈ V and x ≠y}, a set of edges (also called links or lines).

Applications of Graphs :

• Computer Science
• Mathematics
• Physics
• Chemistry
• Biology
• and many more…

One of the most common applications of Graph is finding the Shortest Path which is finding a path between two vertices (or nodes) such that the sum of the weights of its constituent edges is minimized.

Weights can be assigned to each edge of the Graph, which is called Weighted Graphs, and are used to represent structures in which pairwise connections have some numerical values. For example, if a graph represents a road network, the weights could represent the length of each road. There may be several weights associated with each edge, including distance, travel time, or monetary cost. Such weighted graphs are commonly used to program GPS’s, and travel-planning search engines that compare flight times and costs.²

Routing on such a graph can be accomplished effectively using any of the numbers of routing algorithms mentioned above. Different weightings such as distance, cost, or accessibility may be associated with each edge, and sometimes with nodes.³

There are a lot of algorithms that gives the shortest path :

• Dijkstra’s Algorithm
• Bellman-Ford Algorithm
• Floyd-Warshall Algorithm
• Johnson’s Algorithm
• A* (Star) Algorithm
• and more…

Dijkstra’s Algorithm

Google Maps uses Dijkstra’s Algorithm to calculate the Shortest Path between the Source and the Destination.⁴

Dijkstra’s algorithm finds all the shortest paths from the source vertex to every other vertex by iteratively “growing” the set of vertices S to which it knows the shortest path. At each step of the algorithm, the next vertex added to S is determined by a priority queue. The queue contains the vertices in V — S prioritized by their distance label, which is the length of the shortest path seen so far for each vertex. The vertex u at the top of the priority queue is then added to S, and each of its out-edges is relaxed: if the distance to u plus the weight of the out-edge (u, v) is less than the distance label for v then the estimated distance for vertex v is reduced. The algorithm then loops back, processing the next vertex at the top of the priority queue. The algorithm finishes when the priority queue is empty.⁵

I would really like to thank My Professors at Freie Universität Berlin and Technische Universität Berlin, for making me understand this algorithm (and other algorithms) in the best possible way.

Disadvantages of Dijkstra Algorithm

1. The major disadvantage of the algorithm is the fact that it does a blind search thereby consuming a lot of time and waste of necessary resources.
2. It cannot handle negative edges. This leads to acyclic graphs and most often cannot obtain the right shortest path.⁶

Some other applications of the Dijkstra Algorithm⁷

• Social Networking Applications
• Telephone Network
• IP Routing
• Flighting Agenda
• Robotic Path
• and many more…

Packages & Implementation

Thankfully, there are existing Python Packages that already have implemented the Dijkstra Algorithms (and others). I came across two extremely powerful Python Based packages which helped me to explore Graphs.

• NetworkX
• Graph-tool

NetworkX

NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.⁸

Installation

• To Install the Current Release of the NetworkX with pip.

pip install networkx

• To install the Development Release of the NetworkX with pip. (Git should be installed in your system)

git clone https://github.com/networkx/networkx.git
cd networkx
pip install -e .[default]

• NetworkX is a very powerful package with various classes and methods, for now, we will,l stick to the required methods to fetch the shortest path using Dijkstra’s Algorithm.

Implementation

Looking at the above Example, the best path from Vertex 1 to Vertex 9 would be 1 -> 2 -> 4 ->5 ->7 -> 8 -> 9

Using the networkx.dijkstra_path() method the shortest path can be found by passing the Graph, Source and the Destination vertex numbers.

print(nx.dijkstra_path(G, 1, 9))
>>> [1, 2, 4, 5, 7, 8, 9]

Graph-Tool

Graph-tool is an efficient Python module for the manipulation and statistical analysis of graphs (a.k.a. networks). Contrary to most other python modules with similar functionality, the core data structures and algorithms are implemented in C++.

Installation

For Graph-Tool the installation is not as simple as other packages for Windows operating system. Graph-tool is a C++ library wrapped in Python, and it has many C++ dependencies such as Boost, CGAL, and expat, which are not installable via Python-only package management systems such as pip

Steps :

• For Mac and Linux Operating Systems

conda install -c conda-forge graph-tool

• For Windows Operating Systems

1. Install Docker.
2. Open CMD, and type docker images, and a list of existing images will be shown as an output on the console.
3. Type docker pulls Tiago Peixoto/graph-tool to pull the graph-tool package.
4. Type docker image again and graph-tool image should be shown on the console.

5. Run docker run -p 8888:8888 -p 6006:6006 -it -u user -w /home/user tiagopeixoto/graph-tool bash on the CMD console. This will forward the necessary ports to the container, so that your native browser can connect to it at http://localhost:8888/

6. Start the Jupyter Notebook server with jupyter notebook --ip 0.0.0.0

7. Copy Paste one of the URLs from the CMD console to the Browser (Highlighted in the below image).

8. Jupyter Server will start with the graph-tool package installed in it.

9. Open a new Jupyter Notebook, and you are good to go.

Implementation

>>> [1, 2, 4, 5, 7, 8, 9]

Both my implementations from NetworkX and Graph-Tool packages gave the path of 1 -> 2 -> 4 -> 5 -> 7 -> 8 -> 9 which is the best path with the least costs from Source 1to Destination 9.

These algorithms form the spine of the Navigation Systems, of course, the actual implementations are way more complex than this.

Conclusion

It is always interesting to know how things work at the back of one of the most used functionalities (Route Planning with Google Maps). Graph is one of the most powerful structures with innumerable strong applications.

Built-in methods and classes of packages like NetworkX and Graph-tool make implementing Graph and their complex functionalities exceedingly effortless. Both the packages are extremely powerful and have functionalities ranging from changing the properties of Node/Edges up to processing Complex Networks.

References

[1] Google Maps — Wikipedia

[2] Graph theory — Wikipedia

[3] Journey planner — Wikipedia

[4] Dijkstra Algorithm: Key to Finding the Shortest Path, Google Map to Waze | by YOON MI KIM | Medium

[5] graph_tool.search — graph-tool 2.44 documentation (skewed.de)

[6] S Sanan, L Jain, B Kappor, “Shortest Path Algorithm” in International Journal of Application or Innovation in Engineering & Management (IJAIEM), Volume 2, Issue 7, pp 316–217, July 2013

[7] Applications of Dijkstra’s shortest path algorithm — GeeksforGeeks

[8] Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX”, in Proceedings of the 7th Python in Science Conference (SciPy2008), Gäel Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008

[9] My University Lectures at Freie Universität Berlin and Technische Universität Berlin.

Connect

• I will regularly be posting about Python Packages related to Data Science specific to Geospatial Domain, Maps, and more.
• You can connect/follow me on LinkedIn, and on Medium too.
• Feel free to buy me a Coffee!
• You can become a member of Medium by signing up here and if you would like get notified of my articles you can subscribe here.
• If you run into any issues regarding this topic, do not hesitate to comment on the article or DM me on LinkedIn, I will try to revert as fast as possible.

Happy ‘NETWORKx’ing!!!