C.V.

RAMAN GLOBAL UNIVERSITY

Bidyanagar,Mahura,Janla,Bhubaneswar,Odisha-752054
DETAILS:-

NAME:-BISHAL SAHOO
ROLL NO-CSI20018
REGD NO-20010505
GROUP- 3C
ACKNOWLEDGEMENT
FIRSTLY, THANK YOU SIR FOR EVERYTHING.
SECONDLY, WE WOULD LIKE TO THANK OUR
ESTEEMED UNIVERSITY UNDER WHOSE ROOF
WE HAVE STUDIED AND COMPLETED OUR
TASKS, WITHOUT WHICH WE WOULD STAND
NOWHERE. MANY THANKS TO OUR
WONDERFUL LECTURER, SIR FOR GUIDING US
WITH CLEAR INSTRUCTIONS AND ALWAYS
GAVE CONSTRUCTIVE FEEDBACK. HIS
INVOLVEMENT IN THIS ASSIGNMENT TO
HELP US OUT IN ANY ISSUES WITH
REGARDING TO THE MATHMATICAL AND
TECHNIQUES TO WRITE THIS REPORT
RESULTED IN TO THIS BEAUTIFULLY
PRESENTED WORK. HOWEVER, WE WOULD
LIKE TO THANK OUR PARENTS WHO HAVE
BEEN CONSISTENTLY SUPPORTING US AND
ACTING AS A BACKBONE OF OUR SUCCESS.
THEY KEPT SUPPORTING US WITH LOTS OF
CARE, ATTENTION AND SKILLS.
 TOPIC

PATH
FINDING
USING DIJKSTRA’S ALGORITHM
 INTRODUCTION

Pathfinding or pathing is the plotting, by a computer

application, of the shortest route between two points.
It is a more practical variant on solving mazes. This field
of research is based heavily on Dijkstra's algorithm for
finding the shortest path on a weighted graph.
Pathfinding is closely related to the shortest path
problem, within graph theory, which examines how to
identify the path that best meets some criteria
(shortest, cheapest, fastest, etc) between two points in
a large network.Pathfinding method searches
a graph by starting at one vertex and exploring
adjacent nodes until the destination node is reached,
generally with the intent of finding the cheapest route.
Although graph searching methods such as a breadth-
first search would find a route if given enough time,
other methods, which "explore" the graph, would tend
to reach the destination sooner
GRAPY THEORY
In mathematics, graph theory is the study of graphs, which
are mathematical structures used to model pairwise relations
between objects. A graph in this context is made up
of vertices (also called nodes or points) which are connected
by edges (also called links or lines). A distinction is made
between undirected graphs, where edges link two vertices
symmetrically, and directed graphs, where edges link two
vertices asymmetrically. Graphs are one of the principal
objects of study in discrete mathematics.
History

The Königsberg Bridge problem

The paper written by Leonhard Euler on the Seven Bridges of

Königsberg and published in 1736 is regarded as the first
paper in the history of graph theory.[21] This paper, as well as
the one written by Vandermonde on the knight
problem, carried on with the analysis situs initiated
by Leibniz. Euler's formula relating the number of edges,
vertices, and faces of a convex polyhedron was studied and
generalized by Cauchy[22] and L'Huilier,[23] and represents the
beginning of the branch of mathematics known as topology.
More than one century after Euler's paper on the bridges
of Königsberg and while Listing was introducing the concept
of topology, Cayley was led by an interest in particular
analytical forms arising from differential calculus to study a
particular class of graphs, the trees.[24] This study had many
implications for theoretical chemistry. The techniques he
used mainly concern the enumeration of graphs with
particular properties. Enumerative graph theory then arose
from the results of Cayley and the fundamental results
published by Pólya between 1935 and 1937. These were
generalized by De Bruijn in 1959. Cayley linked his results
on trees with contemporary studies of chemical
composition.[25] The fusion of ideas from mathematics with
those from chemistry began what has become part of the
standard terminology of graph theory.
In particular, the term "graph" was introduced by Sylvester in
a paper published in 1878 in Nature, where he draws an
analogy between "quantic invariants" and "co-variants" of
algebra and molecular diagrams:[26]
"[…] Every invariant and co-variant thus becomes
expressible by a graph precisely identical with
a Kekuléan diagram or chemicograph. […] I give a rule
for the geometrical multiplication of graphs, i.e. for
constructing a graph to the product of in- or co-variants
whose separate graphs are given. […]" (italics as in the
original).
The first textbook on graph theory was written by Dénes
Kőnig, and published in 1936.[27] Another book by Frank
Harary, published in 1969, was "considered the world over
to be the definitive textbook on the subject",[28] and
enabled mathematicians, chemists, electrical engineers
and social scientists to talk to each other. Harary donated
all of the royalties to fund the Pólya Prize.[29]
One of the most famous and stimulating problems in
graph theory is the four color problem: "Is it true that any
map drawn in the plane may have its regions colored with
four colors, in such a way that any two regions having a
common border have different colors?" This problem was
first posed by Francis Guthrie in 1852 and its first written
record is in a letter of De Morgan addressed
to Hamilton the same year. Many incorrect proofs have
been proposed, including those by Cayley, Kempe, and
others. The study and the generalization of this problem
by Tait, Heawood, Ramsey and Hadwiger led to the study
of the colorings of the graphs embedded on surfaces with
arbitrary genus. Tait's reformulation generated a new class
of problems, the factorization problems, particularly
studied by Petersen and Kőnig. The works of Ramsey on
colorations and more specially the results obtained
by Turán in 1941 was at the origin of another branch of
graph theory, extremal graph theory.
The four color problem remained unsolved for more than
a century. In 1969 Heinrich Heesch published a method for
solving the problem using computers.[30] A computer-aided
proof produced in 1976 by Kenneth Appel and Wolfgang
Haken makes fundamental use of the notion of
"discharging" developed by Heesch.[31][32] The proof
involved checking the properties of 1,936 configurations
by computer, and was not fully accepted at the time due
to its complexity. A simpler proof considering only 633
configurations was given twenty years later
by Robertson, Seymour, Sanders and Thomas.[33]
The autonomous development of topology from 1860 and
1930 fertilized graph theory back through the works
of Jordan, Kuratowski and Whitney. Another important
factor of common development of graph theory
and topology came from the use of the techniques of
modern algebra. The first example of such a use comes
from the work of the physicist Gustav Kirchhoff, who
published in 1845 his Kirchhoff's circuit laws for calculating
the voltage and current in electric circuits.
The introduction of probabilistic methods in graph theory,
especially in the study of Erdős and Rényi of the
asymptotic probability of graph connectivity, gave rise to
yet another branch, known as random graph theory,
which has been a fruitful source of graph-theoretic results.
PATH FINDING
Pathfinding or pathing is the plotting, by a computer
application, of the shortest route between two points. It is a
more practical variant on solving mazes. This field of research
is based heavily on Dijkstra's algorithm for finding the
shortest path on a weighted graph.
Pathfinding is closely related to the shortest path problem,
within graph theory, which examines how to identify the
path that best meets some criteria (shortest, cheapest,
fastest, etc) between two points in a large network.

At its core, a pathfinding method searches a graph by starting

at one vertex and exploring adjacent nodes until the
destination node is reached, generally with the intent of
finding the cheapest route. Although graph searching
methods such as a breadth-first search would find a route if
given enough time, other methods, which "explore" the
graph, would tend to reach the destination sooner. An
analogy would be a person walking across a room; rather
than examining every possible route in advance, the person
would generally walk in the direction of the destination and
only deviate from the path to avoid an obstruction, and make
deviations as minor as possible.
Two primary problems of pathfinding are (1) to find a path
between two nodes in a graph; and (2) the shortest path
problem—to find the optimal shortest path. Basic algorithms
such as breadth-first and depth-first search address the first
problem by exhausting all possibilities; starting from the
given node, they iterate over all potential paths until they
reach the destination node. These algorithms run in , or
linear time, where V is the number of vertices, and E is the
number of edges between vertices.
The more complicated problem is finding the optimal path.
The exhaustive approach in this case is known as
the Bellman–Ford algorithm, which yields a time complexity
of , or quadratic time. However, it is not necessary to
examine all possible paths to find the optimal one.
Algorithms such as A* and Dijkstra's algorithm strategically
eliminate paths, either through heuristics or through dynamic
programming. By eliminating impossible paths, these
algorithms can achieve time complexities as low as .[1]
The above algorithms are among the best general algorithms
which operate on a graph without preprocessing. However,
in practical travel-routing systems, even better time
complexities can be attained by algorithms which can pre-
process the graph to attain better performance.[2] One such
algorithm is contraction hierarchies.

Dijkstra's algorithm
A common example of a graph-based pathfinding algorithm
is Dijkstra's algorithm. This algorithm begins with a start node
and an "open set" of candidate nodes. At each step, the node
in the open set with the lowest distance from the start is
examined. The node is marked "closed", and all nodes
adjacent to it are added to the open set if they have not
already been examined. This process repeats until a path to
the destination has been found. Since the lowest distance
nodes are examined first, the first time the destination is
found, the path to it will be the shortest path.[3]
Dijkstra's algorithm fails if there is a negative edge weight. In
the hypothetical situation where Nodes A, B, and C form a
connected undirected graph with edges AB = 3, AC = 4, and
BC = −2, the optimal path from A to C costs 1, and the
optimal path from A to B costs 2. Dijkstra's Algorithm starting
from A will first examine B, as that is the closest. It will assign
a cost of 3 to it, and mark it closed, meaning that its cost will
never be reevaluated. Therefore, Dijkstra's cannot evaluate
negative edge weights. However, since for many practical
purposes there will never be a negative edgeweight,
Dijkstra's algorithm is largely suitable for the purpose of
pathfinding.
A* algorithm
A* is a variant of Dijkstra's algorithm commonly used in
games. A* assigns a weight to each open node equal to the
weight of the edge to that node plus the approximate
distance between that node and the finish. This approximate
distance is found by the heuristic, and represents a minimum
possible distance between that node and the end. This allows
it to eliminate longer paths once an initial path is found. If
there is a path of length x between the start and finish, and
the minimum distance between a node and the finish is
greater than x, that node need not be examined.[4]
A* uses this heuristic to improve on the behavior relative to
Dijkstra's algorithm. When the heuristic evaluates to zero, A*
is equivalent to Dijkstra's algorithm. As the heuristic estimate
increases and gets closer to the true distance, A* continues
to find optimal paths, but runs faster (by virtue of examining
fewer nodes). When the value of the heuristic is exactly the
true distance, A* examines the fewest nodes. (However, it is
generally impractical to write a heuristic function that always
computes the true distance, as the same comparison result
can often be reached using simpler calculations – for
example, using Manhattan distance over Euclidean
distance in two-dimensional space.) As the value of the
heuristic increases, A* examines fewer nodes but no longer
guarantees an optimal path. In many applications (such as
video games) this is acceptable and even desirable, in order
to keep the algorithm running quickly.
Sample algorithm
This is a fairly simple and easy-to-understand pathfinding
algorithm for tile-based maps. To start off, you have a map, a
start coordinate and a destination coordinate. The map will
look like X being walls, S being the O being the
this, start,
finish and _ being open spaces, the numbers along the top
and right edges are the column and row numbers:

12345678
XXXXXXXXXX
X___XX_X_X
1X_X__X___
X2XSXX___X
_X3X_X__X_
__X4X___XX
_X_X5X_X__
X_X_X6X_XX
___X_X7X__
O_X___X8XX
XXXXXXXX
First, create a list of coordinates, which we will use as a
queue. The queue will be initialized with one coordinate, the
end coordinate. Each coordinate will also have a counter
variable attached (the purpose of this will soon become
evident). Thus, the queue starts off as ((3,8,0)).
Then, go through every element in the queue, including new
elements added to the end over the course of the
algorithm, and for each element, do the following:

1. Create a list of the four adjacent cells, with a

counter variable of the current element's
counter variable + 1 (in our example, the four
cells are ((2,8,1),(3,7,1),(4,8,1),(3,9,1)))
2. Check all cells in each list for the following
two conditions:
1. If the cell is a wall, remove it from the list
2. If there is an element in the main
list with the same coordinate,
remove it from the cells list
3. Add all remaining cells in the list to the end of the
main list
4. Go to the next item in the list
Thus, after turn 1, the list of elements is this:
((3,8,0),(2,8,1),(4,8,1))

 After 2 turns: ((3,8,0),(2,8,1),(4,8,1),(1,8,2),(4,7,2))

 After 3 turns: (...(1,7,3),(4,6,3),(5,7,3))
 After 4 turns: (...(1,6,4),(3,6,4),(6,7,4))
 After 5 turns: (...(1,5,5),(3,5,5),(6,6,5),(6,8,5))
 After 6 turns: (...(1,4,6),(2,5,6),(3,4,6),(6,5,6),(7,8,6))
  After 7 turns: (...(1,3,7)) – problem solved, end this
stage of the algorithm – note that if you have multiple
units chasing the same target (as in many games – the
finish to start approach of the algorithm is intended
to make this easier), you can continue until the entire
map is taken up, all units are reached or a set counter
limit is reached
Now, map the counters onto the map, getting this:
Now, start at S (7) and go to the nearby cell with the lowest
1 2 3 4 (unchecked
number 5678 cells cannot be moved to). The path
X X X XisX(1,3,7)
traced X X X X->X (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) ->
X _ _ _->X (2,8,1)
(1,8,2) X _ X _->X (3,8,0). In the event that two numbers are
1 X _ X low
equally __X _ _example,
(for _ if S was at (2,5)), pick a random
X 2 X S X –Xthe
direction _ _ lengths
_X are the same. The algorithm is now
_X3X6X6_X_
complete.
__X4X565XX
6X_X5
X4X43X5X_X6
X3XX234X_X7
X2101X56_X
8XXXXXXXXX
Dijkstra's algorithm
Dijkstra's algorithm (/ˈdaɪkstrəz/ DYKE-strəz) 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.[4][5][6]
The algorithm exists in many variants. Dijkstra's original
algorithm found the shortest path between two given
nodes,[6] 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.
For a given source node in the graph, the algorithm finds the
shortest path between that node and every other. [7]: 196–206  It
can also be used for finding the shortest paths from a single
node to a single destination node by stopping the algorithm
once the shortest path to the destination node has been
determined. For example, if the nodes of the graph represent
cities and edge path costs represent driving distances
between pairs of cities connected by a direct road (for
simplicity, ignore red lights, stop signs, toll roads and other
obstructions), Dijkstra's algorithm can be used to find the
shortest route between one city and all other cities. A widely
used application of shortest path algorithms is
network routing protocols, most notably IS-IS (Intermediate
System to Intermediate System) and Open Shortest Path First
(OSPF). It is also employed as a subroutine in other
algorithms such as Johnson's.
The Dijkstra algorithm uses labels that are positive integers
or real numbers, which are totally ordered. It can Be
generalized to use any labels that are partially ordered,
provided the subsequent labels (a subsequent label is
produced when traversing an edge) are monotonically non-
decreasing. This generalization is called the generic Dijkstra
shortest-path algorithm.[8]
Dijkstra's algorithm uses a data structure for storing and
querying partial solutions sorted by distance from the start.
While the original algorithm uses a min-priority queue and
runs in time (where is the number of nodes and is
the number of edges), it can also be implemented
in using an array. The idea of this algorithm is also given
in Leyzorek et al. 1957. Fredman & Tarjan 1984 propose using
a Fibonacci heap min-priority queue to optimize the running
time complexity to . This is asymptotically the fastest
known single-source shortest-path algorithm for
arbitrary directed graphs with unbounded non-negative
weights. However, specialized cases (such as
bounded/integer weights, directed acyclic graphs etc.) can
indeed be improved further as detailed in Specialized
variants. Additionally, if preprocessing is allowed algorithms
such as contraction hierarchies can be up to seven orders of
magnitude faster.
In some fields, artificial intelligence in particular, Dijkstra's
algorithm or a variant of it is known as uniform cost
search and formulated as an instance of the more general
idea of best-first search.[9]
Graph

In one restricted but very common sense of the term,[1]

[2]
a graph is an ordered pair G=(V,E) comprising:
 V a set of vertices (also called nodes or points);

 E ⊆ {{𝒙, 𝒚} | 𝒙, 𝒚 ∈ 𝑽 𝒂𝒏𝒅 𝒙 ≠
𝒚} a set of edges (also called links or lines), which
are unordered pairs of vertices (that is, an edge is
associated with two distinct vertices).
To avoid ambiguity, this type of object may be called
precisely an undirected simple graph.
In the edge {𝒙, 𝒚} , the vertices 𝒙 and 𝒚 are called
the endpoints of the edge. The edge is said to join 𝑥 and
𝑦 and to be incident on 𝒙 and on 𝒚. A vertex may exist in a
graph and not belong to an edge. Multiple edges, not allowed
under the definition above, are two or more edges that join
the same two vertices.
To avoid ambiguity, this type of object may be called
precisely an undirected multigraph.
A loop is an edge that joins a vertex to itself. Graphs as
defined in the two definitions above cannot have loops,
because a loop joining a vertex ‘x’ to itself is the edge (for an
undirected simple graph) or is incident on (for an undirected
multigraph) {x,x}={x} which is not in {{𝒙, 𝒚} | 𝒙, 𝒚 ∈
𝑽 𝒂𝒏𝒅 𝒙 ≠ 𝒚} . So to allow loops the definitions must be
expanded. For undirected simple graphs, the definition of E
should be modified to E ⊆ {{𝒙, 𝒚} | 𝒙, 𝒚 ∈ 𝑽} . For
undirected multigraphs, the definition of 𝜙 should be
modified to E → {{𝒙, 𝒚} | 𝒙, 𝒚 ∈ 𝑽} . To avoid ambiguity,
these types of objects may be called undirected simple graph
permitting loops and undirected multigraph permitting loops,
respectively.
V and E are usually taken to be finite, and many of the well-
known results are not true (or are rather different) for
infinite graphs because many of the arguments fail in
the infinite case. Moreover,V is often assumed to be non-
empty, but E is allowed to be the empty set. The order of a
graph is |V| its number of vertices. The size of a graph is |E|
its number of edges. The degree or valency of a vertex is the
number of edges that are incident to it, where a loop is
counted twice. The degree of a graph is the maximum of the
degrees of its vertices.
A directed graph or digraph is a graph in which edges have
orientations.
In one restricted but very common sense of the
term,[5] a directed graph is an ordered pair G=(V,E)
comprising:

 V, a set of vertices (also called nodes or points);

 E ⊆ {{𝒙, 𝒚} | 𝒙, 𝒚 ∈ 𝑽𝟐𝒂𝒏𝒅 𝒙 ≠ 𝒚} ,
a set of edges (also called directed edges, directed
links, directed lines, arrows or arcs) which are ordered
 pairs of vertices (that is, an edge is associated with
two distinct vertices).

Shortest path problem

54

The shortest path problem can be defined

for graphs whether undirected, directed, or mixed. It is
defined here for undirected graphs; for directed graphs the
definition of path requires that consecutive vertices be
connected by an appropriate directed edge.
The problem is also sometimes called the single-pair shortest
path problem, to distinguish it from the following variations:

 The single-source shortest path problem, in which

we have to find shortest paths from a source
vertex v to all other vertices in the graph.
 The single-destination shortest path problem, in
which we have to find shortest paths from all vertices
in the directed graph to a single destination vertex v.
This can be reduced to the single-source shortest
path problem by reversing the arcs in the directed
graph.
 The all-pairs shortest path problem, in which we
have to find shortest paths between every pair of
vertices v, v' in the graph.
These generalizations have significantly more efficient
algorithms than the simplistic approach of running a single-
pair shortest path algorithm on all relevant pairs of vertices.
Algorithm

Let the node at which we are starting at be called

the initial node. Let the distance of node Y be the
distance from the initial node to Y. Dijkstra's algorithm
will initially start with infinite distances and will try to
improve them step by step.
1. Mark all nodes unvisited. Create a set of all
the unvisited nodes called the unvisited set.
2. Assign to every node a tentative
distance value: set it to zero for our initial
node and to infinity for all other nodes. The
tentative distance of a node v is the length of
the shortest path discovered so far between
the node v and the starting node. Since
initially no path is known to any other vertex
than the source itself (which is a path of
length zero), all other tentative distances are
initially set to infinity. Set the initial node as
current.[15]
3. For the current node, consider all of its
unvisited neighbors and calculate their
 tentative distances through the current node.
Compare the newly calculated tentative
distance to the current assigned value and
assign the smaller one. For example, if the
current node A is marked with a distance of 6,
and the edge connecting it with a
neighbor B has length 2, then the distance
to B through A will be 6 + 2 = 8. If B was
previously marked with a distance greater
than 8 then change it to 8. Otherwise, the
current value will be kept.
4. When we are done considering all of the
unvisited neighbors of the current node, mark
the current node as visited and remove it
from the unvisited set. A visited node will
never be checked again.
5. If the destination node has been marked
visited (when planning a route between two
specific nodes) or if the smallest tentative
distance among the nodes in the unvisited set
is infinity (when planning a complete
traversal; occurs when there is no connection
between the initial node and remaining
unvisited nodes), then stop. The algorithm
has finished.
6. Otherwise, select the unvisited node that is
marked with the smallest tentative
distance,
 set it as the new current node, and go back to
step 3.

How Dijkstra's Algorithm works

Dijkstra's Algorithm works on the basis that any subpath B -> of the shor
also the shortest path between vertices B and D.
D A -> D

Each subpath is the shortest path

Djikstra used this property in the opposite direction i.e we
overestimate the distance of each vertex from the starting
vertex. Then we visit each node and its neighbors to find the
shortest subpath to those neighbors.
The algorithm uses a greedy approach in the sense that we
find the next best solution hoping that the end result is the
best solution for the whole problem.
Example of Dijkstra's algorithm
It is easier to start with an example and then think about the
algorithm.

Start with a weighted graph

Choose a starting vertex and assign infinity path values to all

other devices
Go to each vertex and update its path length

If the path length of the adjacent vertex is lesser than new

path length, don't update it

Avoid updating path lengths of already visited vertices

After each iteration, we pick the unvisited vertex with the
least path length. So we choose 5 before 7

Notice how the rightmost vertex has its path length updated
twice

Repeat until all the vertices have been visited

PROGRAM IN C TO FIND SHORTEST PATH
SOURCE CODE
OUTPUT
Applications
 To find the shortest path
 In social networking applications
 In a telephone network
 To find the locations in the map