APPLICATION OF DJIKSTRA’S ALGORITHM IN GOOGLE MAPS
Abstract
In the first section of this paper, I briefly introduce Dijkstra’s algorithm, its assumptions, the logical mechanism of the algorithm and its applications. In the second section, of the paper I explain the code developed and display screenshots of the code as well as the output generated.
1. Introduction to Dijkstra’s Algorithm
Dijkstra’s Algorithm is an iterative, breadth-first search greedy algorithm that determines the shortest path from one particular node (starting point/source node) in a weighted graph to all the other nodes of the graph.
1.1 Assumptions
Dijkstra’s Algorithm works when all the edges in the graph have positive weights. The Bellman Ford Algorithm however is adapted to deal with negative weighted graphs[1]. In this paper, however, we will only be focusing on Dijkstra’s Algorithm and thus a necessary condition is that the graph has positive weights only.[2]
1.2 Mechanism
· The algorithm starts at the source node and determines the weighted adjacency matrix W of the graph which contains n vertices vi. The weight of the edge connecting vertices vi and vj is denoted as w(i,j)[3].
· The matrix is then defined as the following:
[4]
Here we notice that the w(i,i) of the source node = 0.
· The algorithm has two sets, one containing “visited nodes” and the others containing “unvisited nodes”. Initially all the nodes belong to the “unvisited nodes” set and the “visited nodes” is a null set. The algorithm iterates once over every node in the “unvisited nodes” set. The order in which the algorithm iterates is controlled by a priority queue.[5] The priority is given to those vertices or nodes that have the shortest distance from the source node.
· The algorithm also keeps track of the shortest path and the shortest distance between the source node and every other node. The shortest path is updated when a new shorter path is discovered between the source node and the other node.
· Once the algorithm finds the final shortest path between the source node and another node, then that node is permanently shifted from the “unvisited nodes” set to the “visited nodes” set; consequently, the shortest path and shortest distance are updated too.
· This process continues till the “unvisited nodes” set is a null set. The shortest distance and the shortest path from the source node to all the other vertices can then each be extracted. This way, we have a path that connects the source node to every other node using the shortest possible path to reach each of the nodes.
1.3 Some Application of Dijkstra’s Algorithm
Any optimization problem, that starts from a single source, be it minimizing distance, costs or time, can be solved using the Dijkstra’s algorithm. Some of the use cases of Dijkstra are seen in:
· Social networking apps
They determine the shortest path between connections and suggest users and individual may know.
· Telephone Network
It is used by telephone and cellular networks for efficient routing management.[6]
· Flighting Agenda
Many travel agents use the Dijkstra’s algorithm to determine the minimum time taken to reach a destination from a starting point given all the information regarding all airports and flights- flight number, origin airport and destination airport, departure and arrival times.[7]
· Robots and drones
Many robots or drones are used to deliver packages in a short time span. The automated drones/machines are guided by Dijkstra’s algorithm to reach the destination in the least amount of time.
· Evacuation Routes
There has been work on replacing traditional fixed signs of the fire evacuation systems to more intelligent fire evacuation system which is developed using Dijkstra’s algorithm. It identifies the source of the fire and thereby determines the best route to evacuate the people in the fire region safely.[8]
· Geographic Information system
The Dijkstra’s Algorithm is used to find the minimum distance between the start location and the destination.
2. Application of Dijkstra’s Algorithm in Google Maps
In this paper, I have elaborated on the last application of Dijkstra’s Algorithm mentioned above-in Geographic Information systems (GIS) like Google Maps.
I have used a data set that gives a matrix of the road distance (in Km) between major cities in India(http://www.lemuir.com/Assets/pdf/roaddistance.pdf) to develop an algorithm that determines the shortest Kilometer route between the start location and the destination entered by the user.
2.1 Code
Below I have attached screenshots of the code developed. The algorithm allows users to find the shortest route and the shortest distance between 47 major Indian cities.
The logic of the code resonates with the mechanism as explained in section 1.2 of the paper.
I have managed to comment the logic alongside the code in the figures for more detail.
The sample output has given the shortest path and distance in Kms from the start location (Bangalore) and the end location (Lucknow).
It is evident that the algorithm determined route is indeed at least shorter (1895 Km) than the direct route from Bangalore to Lucknow (1934 Km) as given in the matrix of road distance of major Indian cities.
I chose Bangalore, Lucknow and Hyderabad for the purpose of these examples; however, this code allows you to choose from vast variety of 47 cities.
3. Conclusion
This code closely emulates how GIS services like Google Maps make use of Dijkstra’s Algorithm to return the shortest route from the start location to the end location. Sometimes, these maps choose to determine the shortest path in terms of time rather than distance too.
Thus the Dijkstra’s algorithm is versatile in the sense that it can be used to optimize various different variables depending on the requirement of the service.
4. References
http://www.lemuir.com/Assets/pdf/roaddistance.pdf
Koshy, Thomas. Discrete mathematics with applications. Elsevier, 2004.
Magzhan, Kairanbay, and Hajar Mat Jani. “A review and evaluations of shortest path algorithms.” International journal of scientific & technology research 2.6 (2013): 99–104.
Ryder, A. (2018, April 01). Dijkstra’s algorithm: Application, Complexity, Implementation, Explanation. Retrieved December 11, 2020, from https://iq.opengenus.org/dijkstras-algorithm-finding-shortest-path-between-all-nodes/
Shortest Path with Dijkstra’s Algorithm. (n.d.). Retrieved December 11, 2020, from https://bradfieldcs.com/algos/graphs/dijkstras-algorithm/
Y. Xu, Z. Wang, Q. Zheng and Z. Han, “The Application of Dijkstra’s Algorithm in the Intelligent Fire Evacuation System,” 2012 4th International Conference on Intelligent Human-Machine Systems and Cybernetics, Nanchang, Jiangxi, 2012, pp. 3–6, doi: 10.1109/IHMSC.2012.7.
[1] Magzhan, Kairanbay, and Hajar Mat Jani. “A review and evaluations of shortest path algorithms.” International journal of scientific & technology research 2.6 (2013): 99–104
[2] Magzhan, Kairanbay, and Hajar Mat Jani. “A review and evaluations of shortest path algorithms.” International journal of scientific & technology research 2.6 (2013): 99–104
[3] Koshy, Thomas. Discrete mathematics with applications. Elsevier, 2004.
[4] Koshy, Thomas. Discrete mathematics with applications. Elsevier, 2004.
[5] Shortest Path with Dijkstra’s Algorithm. (n.d.). Retrieved December 11, 2020, from https://bradfieldcs.com/algos/graphs/dijkstras-algorithm/
[6] Shortest Path with Dijkstra’s Algorithm. (n.d.). Retrieved December 11, 2020, from https://bradfieldcs.com/algos/graphs/dijkstras-algorithm/
[7] Ryder, Dijkstra’s algorithm: Application, Complexity, Implementation, Explanation 2018
[8] Y. Xu, Z. Wang, Q. Zheng and Z. Han, “The Application of Dijkstra’s Algorithm in the Intelligent Fire Evacuation System,” 2012 4th International Conference on Intelligent Human-Machine Systems and Cybernetics, Nanchang, Jiangxi, 2012, pp. 3–6, doi: 10.1109/IHMSC.2012.7.