www.ijcrt.

org © 2020 IJCRT | Volume 8, Issue 12 December 2020 | ISSN: 2320-2882

IMPLEMENTATION OF DIJKSTRAS
ALGORITHM TO FIND THE SHORTEST PATH
IN GOOGLE MAPS
1
Sathyapriya.S, 2Kavin.M.K, 3Mythreye Rakshana.S
1
Assistant Professor, 2Pg Scholar, 3Pg Scholar
1
Department of Mathematics
1
Sri Krishna Arts and Science College, Coimbatore, India

Abstract: In this paper, by using Dijkstras algorithm, we define the shortest path in online network services by applying the
principle of graph theory. The shortest path problem is an approach to finding the shortest and fastest path or route from a
starting point to an ending point. This illustrates how the path can be visualised in the essence of vertices and edges as graphs.
The smallest distance from the starting point to the final destination is measured using Google Maps in our research paper. Our
main objective in this paper is to achieve the method of running google map services using a graph theoretical approach to
evaluate the shortest journey and its implementation using the Dijkstras algorithm in computer science. We also give diagrams
and prove certain findings in this paper.

Keywords - Distance graph, Online network services, Shortest route problem, Dijkstras algorithm

1. INTRODUCTION:

A branch of discrete mathematics is graph theory. Graph theory in mathematics and computer science is the study of graphs
used to model pair wise relationships between objects that are mathematical structures. In providing problem solving techniques,
there is wide use of graphs because it gives an intuitive way before formal description is given. Two problem areas are taken into
consideration in order to evaluate the graph theory application.
1- Classical problem
2- Problems from applications

With the aid of graph theory, the classical problem is described as connectivity, cuts, paths and flows, colouring problems,
and the theoretical aspect of graph drawing. Whereas application problems emphasis experimental study and the implementation
of graph theory algorithms in particular. In terms of implementation, graph drawing is a key subject, as automatic drawing graph
generation has important applications in key computer science technology, such as database design, software engineering, circuit
design, network design and visual interfaces.
Graph theory principles are extensively used by applications of computer science. For example, in computer science research
areas such as data mining, image segmentation, clustering, image capture, networking, etc., a data structure can be constructed in
the form of a tree that uses vertices and edges in turn. Similarly, using graph principles, simulation of network topologies can be
accomplished. In the same way, scheduling is used in resource allocation, the most significant concept of graph colouring. In
huge applications, paths, walks and circuits in graph theory are often used, say travelling salesman problem, concepts of
database design, networking of resources. This leads to new algorithms and new theorems being developed that can be used in
enormous applications.

2. GRAPH THEORY:

Graphs provides many way to represent many kinds of mathematical objects. Usually a graph is made up of:
1- A set of vertices
2- A set of edges
Restrictions are imposed on the type of edges we authorise, depending on the specific situation. Directed edges are applied for
certain problems and undirected edges are applied from one vertex to another for other problems. So graphs provide us with
many tools and versatility when identifying and solving a problem of real life. Graphs have many attributes, some of which are

IJCRT2012240 International Journal of Creative Research Thoughts (IJCRT) www.ijcrt.org 2312

www.ijcrt.org © 2020 IJCRT | Volume 8, Issue 12 December 2020 | ISSN: 2320-2882

Provides abstracted view

Establishes relationship among objects Balancing
Modeling
Decision -making ability
Structural arrangement of various objects
Easy modification or change in the existing system

3. GRAPH THEORY AND SHORTEST ROUTE PROBLEM:

A Graph G consists of pair (V(G), E(G)) where V(G) is a non-empty finite set whose elements are vertices and E(G) is a set of
unordered pairs of distinct elements of V(G). The number of vertices in a graph is called the order and number of edges in a
graph is called the size. The degree of vertex denoted by deg(v) . A directed graph in which each edge is represented by an
ordered pair of two vertices. (Vi, Vj) denotes an edge from Vi to Vj from first vertex to second vertex. A graph G=(V,E) with no
loops and no multiple edges or parallel edges is called simple graph. A graph is said to be acyclic graph if it has no cycles. An
acyclic graph which is connected is called a tree and if one or more of the edges disconnected then the acyclic graph is a called a
forest.

The problem of finding a path between two vertices in a graph in graph theory in such a way that the sum of its weights is
reduced from its constituent edges is called the shortest route problem. In network analysis, the Shortest Route problem is a basic
problem. Graph is a pictorial representation of the problem with the shortest route that includes a set of vertices and edges. Like
nodes, vertices are named. The pair of vertices are connected by edges. By moving from one vertex to another vertices, it is
possible to walk along the edges depending on whether one can walk along the edges on both sides or on only one side as the
graph is directed or undirected graph. To estimate the smallest route from source to destination, the lengths of the edges are
called weights.

4. APPLICATION OF GRAPH THEORY IN COMPUTER SCIENCE

In the field of computer science, graph theory is playing an increasingly significant role. Any software that needs to be
developed, any application that has to be checked, makes it easy to use graphs. Its significance is derived from the fact that
control flow and data flow can be represented in terms of directed graphs for any programme. In microchip design, circuitry,
scheduling problems in the operating system, file management in the database management system, data flow control between
networks and networks, graph theory is also used. The theory of graphs allowed the field of computers develop its own
computational algorithms for graphs. These algorithms are used to formulate solutions for many applications in the field of
computer science.

5. GRAPH THEORY IN GOOGLE MAPSERVICES

The map is a pictorial depiction on a flat surface of an area depicted. Detailed characteristics of a geographical area such as
borders, paths, physical features, topography, climates, and time resources are demonstrated in the map effort. The problem is
explained manually, which takes time, and using mathematical methods such as shortest route algorithms can easily solve this
difficulty. Google Maps allows to hit the destination from one place to another. Graph theory is the analysis of points and lines
in which vertices are considered a set of points. The edges are called lines that link points. Depending on the walk to one side or
both sides, graphs may be either guided or undirected. Weights from one intersection to another are called the lengths of the
edges, which is the optimization expense used to determine the smallest path from source to destination. From the beginning
point to the end point, Google Map defines all possible routes. A server will show the shortest and quickest path. The distance in
kilometers shows all possible routes between Avadi and Ambattur in Figure 1. Three potential routes are sorted by a google map,
out of which the shortest route is highlighted in blue in 23 minutes, with a distance of 9.4 km.

Figure 1. Google map

IJCRT2012240 International Journal of Creative Research Thoughts (IJCRT) www.ijcrt.org 2313

www.ijcrt.org © 2020 IJCRT | Volume 8, Issue 12 December 2020 | ISSN: 2320-2882

6. G OOGLE M APS DIGITAL M APPING SERVICES:

We have tried to find the distance on G-Maps several times, from one city to another or from your place to the nearest desired
location. There is the Shortest Path Algorithm, since there are different routes/paths connecting them, so the minimum distance
needs to be shown, so Dijkstras Algorithm is used to find the minimum distance along the path between two places.
Google Maps is a Google-developed web mapping tool. It includes satellite imagery, aerial photography, street maps, interactive
360° street views, real-time traffic conditions, and route planning for walking, car, bicycle, air (beta) and public transport travel.
In2020, more than 1 billion individuals used Google Maps every month. Google Maps started as a C ++ desktop application.
The company was purchased in October 2004 by Google, which turned it into a web application. In February2005, Google Maps
was released. The front end of the service utilises JavaScript, XML, and Ajax. Google Maps provides an API that enables maps
to be embedded on third-party websites, and provides corporations and other organisations in many countries around the world
with a locator.

Figure 2:Flow diagram of Dijkstra’s algorithm

7. DIJKSTRAS ALGORITHM:

The Dijkstra algorithm is one of the most common algorithms for solving many shortest path issues with non-negative edge
weight in the graphs, i.e. finding the shortest distance on a graph between two vertices. Computer scientist Edsger W. Dijkstra
invented it in 1956 and published it three years later. Dijkstras algorithm is used for finding the shortest distance between
nodes.The algorithm generates a tree of shortest paths in the graph from the starting vertex, the source, to all other points. By
constructing a collection of nodes that have a minimum distance from the source, the algorithm finds a shortest path tree from a
single source node.
The graph has the following
I. Vertices, or nodes, denoted in the algorithm by v or u.
II. Two nodes are bound by weighted edges: (u,v) denotes an edge, and w(u,v)denotes its weight. The weight for every edge is
written in grey in the diagram on the right.

8. ALGORITHM STEPS:

I.Set the distance of all vertices = infinity except the source vertex. Set the distance of the source = 0.
II.Push the source vertex in the form of a min-priority queue (distance, vertex), as the min-priorityqueue comparison
would be based on the distances of the vertices.
III.Pop the vertex with the minimum distance from the priority queue (at first the popped vertex = source).
IV.In the case of current vertex distance + edge weight <next vertex distance, change the distance of the connected vertices to the
popped vertex, then shift the vertex to the priority queue with the new distance.
V.If the popped vertex is visited before just proceed without using it.
VI.Apply the same algorithm again until there is an empty priority list.

IJCRT2012240 International Journal of Creative Research Thoughts (IJCRT) www.ijcrt.org 2314

www.ijcrt.org © 2020 IJCRT | Volume 8, Issue 12 December 2020 | ISSN: 2320-2882
9. SHORTEST PATH PROBLEMS:

A primary problem in graph theory is the shortest path. It can also be one of the main problems in network research. Generally,
we use graphs in order to depict the shortest path problem. A graph is an abstract mathematical object comprising sets of vertices
and edges. Pairs of vertices are bound by edges. It is possible to walk along the edges of a graph by moving from one vertex to
other vertices. It defines whether the graph is a directed graph or an undirected graph, depending on whether or not one can walk
along the edges on both sides or on just one side. Moreover, edge lengths are sometimes referred to as weights, and weights are
typically used to measure the shortest path from one point to another point. The theory of graphs can be extended to various
forms of situations in the real world. For example, we can use a graph to represent a map, where vertices represent towns and
edges represent routes that link the towns. When routes are one-way, the graph is directed; It would otherwise be undirected.
There are three types of short path, Which are: Single source shortest path (SSSP) algorithms; Single destination shortest path
(SDSP) algorithms; All-pairs shortest path (APSP) algorithms. There exist different types of algorithms that solve the shortest
path problem that uses genetic algorithm which include: Dijkstras Algorithm; Floyd-Warshall Algorithm; Bellman-Ford
Algorithm; and Alternative path algorithm.

10. PROPOSED ALGORITHM:

This is pseudocode for Dijkstras rule, mirroring Python syntax. It will be employed in order to implement the rule in any
language.

11. PROBLEM:

Extract the graph from the google map.The weights in terms of cost are denoted on edges from one intersection to other. Plot the
points where the lines meet at intersection as vertices. Label the vertices as A, B, C, D, E, F, G, H, I, J, K, L and M respectively.
Mark the directions mentioned in the google map for avenues and lanes.

Figure 3. Distance graph G

The weights of the graphs differ due to parameters like speed limits, road work distance. Latest updates on traffic data and
various data are sent to server and these can be utilized in calculating quickest way from one place to other.

IJCRT2012240 International Journal of Creative Research Thoughts (IJCRT) www.ijcrt.org 2315

www.ijcrt.org © 2020 IJCRT | Volume 8, Issue 12 December 2020 | ISSN: 2320-2882
Table : Finding the Shortest Path Using Dijkstras Algorithm

Steps Selected D(A) D(B) D(C) D(D) D(E) D(F) D(G) D(H) D(I) D(J) D(K) D(L) D(M)
Vertex
1 K ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞

2 I ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2 ∞ 0 3 ∞

3 E,L ∞ ∞ ∞ ∞ 3 ∞ ∞ ∞ 2 5 0 3 ∞

4 J 7 ∞ ∞ ∞ 3 ∞ ∞ ∞ 2 5 0 3 8

5 A 7 ∞ ∞ ∞ 3 ∞ ∞ ∞ 2 5 0 3 8

6 M 7 15 ∞ ∞ 3 ∞ ∞ ∞ 2 5 0 3 8

7 H 7 15 ∞ ∞ 3 ∞ ∞ 14 2 5 0 3 8

8 B 7 15 ∞ 19 3 ∞ 16 14 2 5 0 3 8

9 G 7 15 19 19 3 18 16 14 2 5 0 3 8

10 F 7 15 19 19 3 18 16 14 2 5 0 3 8

11 C,D 7 15 19 19 3 18 16 14 2 5 0 3 8

The cumulative sum of first route direction is given by K+I+E+A+B+C+D =24 and the cumulative sum of second route
direction is given by K+L+N+H+D =19. Here the second route is the shortest route which is the optimum.

12. CONCLUSION:
In this paper, Dijkstras algorithm is used to find out the shortest path in a graph. The shortest route problem in graph theory
determines the smallest and quickest route from the source to destination.
In our research paper we define the new graph theoretical approach for estimating minimum cost paths. It is therefore quite clear
that computer power must be combined with the ingenuity of mathematical methods to improve the speed of manipulation , so
we use Dijkstras algorithm to find all possible routes.

13. REFERENCES:

[1] Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E. (April 1990). "Faster Algorithms for the Shortest
Path Problem" Journal of the ACM
[2] Avdhesh, K.S., & Sourabh, K., (2013). Finding of Shortest Path from Source to Destination by traversing every Node in
wired Network International Journal of Engineering and Technology, Vol 5, 2655-2656.
[3] N. Biggs, E. Lloyd, and R. Wilson, Graph Theory 1736-1936, Clarendon Press Oxford, 1976.
[4] Deo, Narsingh (1974). Graph Theory with Applications to Engineering and Computer Science, Englewood, New Jersey:
Prentice-Hall.
[5] Kairanbay, M., &Hajar, M.J., (2013). A Review and Evaluations of Shortest Path Algorithms. International Journal of
Scientific and Technology Research, Vol 2, 99-101.
[6] Mojo H., (2016). Graph theory. Available at www.en.m.wikipedia.org/wiki/Graph_Theoy. Retrieved 9th August 2016.
[7] Merriam W., (2016). Definition of Graph. Available at www.merriam-webster.com/Dictionary/graph. retrieved 13th July,
2016.
[8] Rishi Pal Sing, Vandana, “ Application of Graph Theory in Computer Science and Engineering,” International Journal of
Computer Applications (0975 – 8887) Volume 104 – No.1, October 2014.
[9] Sudhakar, T.D.,Vadivoo, N.S., Slochanal, S.M.R., Ravichandran, S. Supply restoration in distribution networks using
Dijkstra's algorithm. International Conference on Power System Technology, Signapure. 2004 (PowerCon 2004)

IJCRT2012240 International Journal of Creative Research Thoughts (IJCRT) www.ijcrt.org 2316