DISCRETE MATHAMETHICS

ALGORITHM MAKES GOOGLE

MAP POSSIBLE

Submitted To:
Submitted By:
Mrs. Pooja Yadav
Manik Sharma (2K20/CO/254)
Manjeet Vats( 2K20/CO/257)
 Table of Content

Section Content Page No.

1. Acknowledgement 3

2. Abstract 4
3. Introduction 5

4. Aim 6

5. Objective 6
6. Hardware & Software requirement 6
7. Concepts used 7
8. Full code 8
9. Module detail 17
10. Conclusion 28
11. Bibliography 29
 ACKNOWLEDGEMENT

I am very thankful to my teacher who gave me such a great opportunity to discover and research this
project
I always wanted to have experience in any kind of research so that I would be prepared for my future
projects.
I am also thankful to my college head deans who came up with such interesting and new ideas of teaching
online.
This project became my partner in my free time, which now I can use it perfectly for my benefit.

I have taken efforts in this project. However, it would not have been possible
without the kind support and help of many individuals and organizations. We
would like to extend my sincere thanks to all of them. We are highly indebted to
mrs.indufor their guidance and constant supervision as well as for
providing necessary information regarding the project & also for their support in
completing the project.
I would like to express my special gratitude and thanks to the Department of
Computer Engineering for providing us the golden opportunity to do this project.
My thanks and appreciation also go to people who have willingly helped me out
with their abilities.
 ABSTRACT

Design techniques based on classical algorithms have often proved useful. They are
especially useful for recent innovations on large-scale problems like travel itineraries and
routing challenges. For instance, Dijkstra’s algorithm is used to find the shortest path
between nodes in a graph, such as road networks. However, the process of partitioning a
road network can speed up algorithms by shrinking the part of the graph that is searched
during computation. 
Discrete mathematics plays the significant role in big data analytics.It is an excellent tool
for improving reasoning and problem-solving abilities and an exciting and an exciting
and appropriate vehicle for working towards and achieving the goal of educating
informed citizen who are better able to function in our increasingly technological society

.
 INTRODUCTION

Google Maps is based on a very simple but incredibly effective algorithm: the
Dijkstra algorithm. It takes its name from its inventor, EdsgerDijkstra, one of the
pioneering founders of modern computing.Google Maps uses Dijkstra's
Algorithm of finding the shortest paths between nodes in a graph, which may
represent, for example, road networks.Over recent years, we’ve seen various
problems about maps but we can use google maps for easily solve. Just like the
GPS (Global Positioning System) tracking systems play an import role in the
position-aware applications. For the cost issue, most of these systems uses the
Google MAP to display. with this we find shortest path for visited areas of the city.

 OBJECTIVE

● Saving the program name and scheduling them at their respective timings andday.
● To find shorted travelling area.
● Use GPS to find criminal location.
● Indicate trafficking areas.
● To organize the world’s information and make it universally accessible and use.

Recommended Hardware Requirements

Processor: intel i5 9th gen

RAM: 4 GB
Hard disk: 10 GB
Monitor: VGA/SVGA

Software Requirements
Language: C++
Operating System: Windows 7, 8, 9, 10, XP
Compiler: GNU GCC
IDE: CodeBlock
 CONCEPTS USED
1. Array: An array is a collection of items stored at contiguous memory locations. The ideais
to store multiple items of the same type together. (i.e. Name[], day[], pin[], company[][]).

2. Functions: A function is a block of code which only runs when it is called. You can pass
data, known as parameters, into a function.(i.e. input(), output(), calculate_trp(),
calculate_amount(), return_day()).

3. Pointers: A pointer however, is a variable that stores the memory address as its value.
A pointer variable points to a data type (like int or string ) of the same type. (i.e.*sec,
*days)

4. Classes: A class in C++ is the building block, that leads to Object-Oriented programming. It
is a user-defined data type, which holds its own data members and member functions, which
can be accessed and used by creating an instance of that class. A C++ class is like a
blueprint for an object. (i.e. class program, sponsor, trp_class, amount).

5. Inheritance: The capability of a class to derive properties and characteristics from another
class is called Inheritance. Inheritance is one of the most important feature of Object
Oriented Programming.(i.e. class program inherited from trp_class,amount and sponsor
class so, its multipleinheritance).

6. File Handling: File handling provides a mechanism to store the output of a programin
afile and to perform various operations on it. A stream is an abstraction that represents a
device on which operations of input and output are performed.( i.e. ifstream, ofstream,
fstream).

7. Switch statement: A switch statement allows a variable to be tested for equality against a
list of values. Each value is called a case, and the variable being switched on is checked for
each case. (i.e. switch (choice)).

8. Loops: A loop is used for executing a block of statements repeatedly until a particular
condition is satisfied. (i.e. while, for, do while loops used inproject).
 FULL CODE
// A C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph
#include <iostream>
using namespace std;
#include <limits.h>

// Number of vertices in the graph

#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
intminDistance(intdist[], boolsptSet[])
{

// Initialize min value

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false &&dist[v] <= min)
min = dist[v], min_index = v;

returnmin_index;
}

// A utility function to print the constructed distance array

voidprintSolution(intdist[])
{
cout<<"Vertex \t Distance from Source" <<endl;
for (int i = 0; i < V; i++)
cout<< i << " \t\t"<<dist[i]<<endl;
}

// Function that implements Dijkstra's single source shortest path algorithm

// for a graph represented using adjacency matrix representation
voiddijkstra(int graph[V][V], intsrc)
{
intdist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i

boolsptSet[V]; // sptSet[i] will be true if vertex i is included in shortest

// path tree or shortest distance from src to i is finalized
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0

dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in the first iteration.
int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

// Update dist value of the adjacent vertices of the picked vertex.

for (int v = 0; v < V; v++)

// Update dist[v] only if is not in sptSet, there is an edge from

// u to v, and total weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] &&dist[u] != INT_MAX
&&dist[u] + graph[u][v] <dist[v])
dist[v] = dist[u] + graph[u][v];
}

// print the constructed distance array

printSolution(dist);
}

// driver program to test above function

int main()
{

/* Let us create the example graph discussed above */

int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
 { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);

return 0;
}

OUTPUT

DESCRIPTION OF WORK

EXAMPLE

QUESTION . "What's the shortest way to travel from Rotterdam to Groningen?," Dijkstra
said. "It is the algorithm for the shortest path

ANSWER. The easiest way to explain Dijkstra's algorithm is probably with an example. Take
the graph below, where the numbers given are the weights of each connection. (A weight
could be a simple distance or really any relative cost associated with traversing a particular
connection that we're seeking to minimize.) To start, we assign s, our starting position, the
value 0. It takes 0 miles (or whatever) to get here because it's the beginning position. Next, we
look at the neighboring nodes of s, which we can imagine as a sort of frontier to be
explored.route.jpg

In the first iteration, we look to the closest node, which is 1 unit away. We assign a label to the
node with that value, a, and look onward at the next frontier nodes and their respective
distances. b is 1 away (2 from the beginning), c is 2 away (3 from the beginning), and we also
have d, which is 2 from the beginning. Since we're after the shortest path from the beginning,
we're forced to move to d from s (2 units), and we assign a value of 2 to d. On
the next iteration of the algorithm, from d we look ahead to c, which is 10 away (12 from s),
but we also look again from our outpost at a, where we can still get to c in 2 (3 from the
beginning) and b in 1 (2 from the beginning). We set up our next outpost at b and assign it a
label of 2 (2 moves from the start).
Our explorer stationed at b is in for a disappointment. The only possible move to t is 10 units
away (12 from the beginning). And this is more than the 2 units from a to c (3 from the
beginning) and the same as a trip fro
d, a possibility we can now safely discard (having arrived at c in only 3 units,
rather than the 12 required via d). Now, we're at c and if this seems complicated it's really not.
We're just making cautious, tentative steps from node to node, while being forced by the
algorithm to always consider the shortest path from the start.

Finally, we again look from b to t, again noting the total path as being 12. Meanwhile, the final
jump from c costs 1, for a total shortest path distance of 4.And so an incredibly complex—
explosively complex.
 CONCLUSION
Now, I would like to conclude my project with some advantages and
disadvantages of it.

ADVANTAGES
• For finding current location
• For finding the distance between two points
• Finding the shortest path
• Business listings
• Searching places
• Reduces travelling difficulties

DISADVANTAGES

1. This project has not great presentation of the records.

2. This project is not perfectlyoptimized.

NAVIGATION

Google maps uses graphs for building transportation systems, where

intersection of two(or more) roads are considered to be a vertex and the road
connecting two vertices is considered to be an edge, thus their navigation
system is based on the algorithm to calculate the shortest path between two
vertices.
IMPLEMENTATION OF SHORTEST PATH USING DIJKSTRA’S
ALGORITHM :

This algorithm is used to find the shortest distance between source vertex
and destination vertex when edges have different weights.

SHORTEST PATH OF ALL VERTICES IN THE ABOVE GRAPH

TAKING ‘0’ NODE AS THE SOURCE VERTEX.

code
output
 BIBLIOGRAPHY

● https://en.wikipedia.org/wiki/Target_rating_point
● https://timesofindia.indiatimes.com/What-is-TRP-and-how-it-is-
calculated/articleshow/11816.cms
● Book: SumitaArora