VIT Bhopal University

Dijkstra's
ALGORITHM
By Group 3

Course:-MAT2002 Faculty:- Prof. Dr. A. Manickam

 CONTENTS
Introduction to Phases of examples of
Dijkstra's Algorithm Dijkstra's Algorithm dijkstra's algorithm

Advantages and
disadvantages

Prim's, kruskal's and Applications of

conclusion
dijkstra's Dijkstra's algorithm
 Introduction to
Dijkstra's Algorithm
DIJKSTRA'S ALGORITHM
It's a graph search algorithm that
solves the single-source shortest
path problem for a graph with
non-negative edge path costs,
producing a shortest path tree.
This algorithm finds the path with
the lowest cost (i.e. the shortest
path) between that vertex and
every other vertex.
Approach: Greedy
DIJKSTRA'S ALGORITHM
The Dijkstra's Algorithm works on the following formula:-

if, d[u] + c(u,v) < d[v]

then, d[v] = d[u] + c(u,v)

Where,
d[u] = distance of the chosen vertex,
c(u,v) = cost from u to v,
d[v] = initial distance of v

This is also known as 'Relaxation'.

Phases of Dijkstra's
Algorithm
Problem
Using Dijkstra's Algorithm, find the shortest path between the
vertices a to z in the following weighted graph.
Step 01 - Remove all the loops
Step 02 - Remove all the parallel edges between two vertices
except the one with the least weight
 Step 03 - Create a weight matrix table

1. Set 0 to the source vertex and infinite to the remaining

vertices.
2. Mark the smallest unmarked value and mark that vertex
3. Find the vertices which are directly connected to marked
vertex and update all.

Repeat 2 and 3 till we reach destination vertex.

Derive the shortest
path using weight
matrix table.
Problems related to
Dijkstra's Algorithm
 Problem
Find the shortest path cost from vertex 1 to every other vertex in the
given directed weighted graph.
7
2 4
2 1

1 2
1 6
4 5
3
3 5
Step 1
after selecting vertex 1, check for direct paths.

7
2 4
2 1

1 2
1 6
4 5
3
3 5
Step 2
Since the vertex '2' is the shortest, select it and relax other vertices.

7
∞ 7

2 4
2
1
1
4
3
4 3
Step 3
Since the vertex '3' is the shortest, select it and relax other vertices.

2 9
7
2 4
2
1
1

4
3
3 5
6
3 ∞
Step 4
now select the vertex '5' and relax other vertices.

2 9 8
7
2 4
2
1 2
∞ 11
1 6
4 5
3
3 5
3 6
Step 4
Since the vertex '4' is the shortest, select it and relax other vertices.

2 8
7
2 4
2 1

1 2
1 6 11 9
4 5
3
3 5
3 6
now all the vertices are relaxed, hence we derive the following data.

these are the shortest paths

to all the other vertices from
vertex '1'.
 Problem
Find the shortest paths between K and L in
the given directed graph using Dijkstra's
Algorithm.
 Step 1
Include the vertex K and determine all the direct paths from K to all
other vertices without going through any other vertex.

Step 2
Include the vertex in S which is nearest to K and determine shortest paths to
all vertices through this vertex and update the values. The closest vertex is c.
Step 3
continue to find shortest path vertices. now the shortest path is 'a'

Step 4
continue to find shortest path vertices. now the shortest path is 'b'
Step 5
continue to find shortest path vertices. now the shortest path is 'd'

Since there are n-1 vertices in S, hence we have found the

shortest path from K to all other vertices.

Hence, the shortest path from K to L is {K, c, b, L) and the

distance is 8.
Pros and Cons of
Dijkstra's
algorithm
 ADVANTAGES DISADVANTAGES
It has little complexity which is It does an obscured exploration that
almost linear. consumes a lot of time while
It can be used to calculate the processing.
shortest path between a single It is unable to handle negative edges
node to all other nodes and a As it heads to the acyclic graph, so
single source node to a single can’t achieve the accurate shortest
destination node by stopping the path.
algorithm once the shortest Also, there is a need to maintain
distance is achieved for the tracking of vertices, have been
destination node. visited.
It works for directed as well as
undirected weighted graphs
Prim's, Kruskal's
and Dijkstra's
Algorithms
 Prim's Dijkstra's Kruskal's
Algorithm Algorithm Algorithm
Prim' s algorithm Dijkstra's algorithm Kruskal's algorithm
constructs a minimum constructs a shortest path constructs a minimum
spanning tree for the tree starting from some spanning tree for the
graph, which is a tree source node. A shortest path graph, which is a tree
that connects all nodes tree is a tree that connects that connects all nodes
in the graph and has the all nodes in the graph back to in the graph and has the
least total cost among the source node and has the least total cost among
all trees that connect property that the length of all trees that connect all
all the nodes. any path from the source node the nodes, however the
to any other node in the graph greedy approach is used
is minimized. differently than Prim' s
Algorithm.
 Prim's Dijkstra's Kruskal's
Algorithm Algorithm Algorithm

It is used for: it is used for: it is used for:

Electrical systems digital mapping systems tv network
network designing telephone network tour operations
designing protocols flighting agenda landing cables.
in network cycles
Applications of
Dijkstra's
Algorithm
 Telephone Network

in a telephone network, each line

has a bandwidth . The bandwidth of
the transmission line is the highest
frequency that line can support.
If we imagine a city to be a graph,
the vertices represent the switching
stations, and the edges represent
the transmission lines.
it can fall into the category of
shortest distance problem, for
which the Dijkstra is can be used.
 Digital Mapping Services in Google Maps

there are various routes/paths

connecting to various cities but it
has to show the minimum distance,
so Dijkstra’s Algorithm is used to
find the minimum distance between
two locations along the path.
 Example
Here 'D' is the Goal Node.
A
A C E D = 2 + 4 + 5 = 11
2 3
ABED=3+1+5=9
C 1 B
4
E AbD=3+6=9

10 5 6
A C d = 2 + 10 = 12

Either of the cases where we obtain the

D
path cost = 9 , is an optimal solution.
 Flighting Agenda
If a person needs software for making an agenda of flights for customers. The agent
has access to a database with all airports and flights. Besides the flight number,
origin airport, and destination, the flights have departure and arrival time.
Specifically, the agent wants to determine the earliest arrival time for the
destination given an origin airport and start time. There this algorithm comes into use.
 Designate File Server
To designate a file server in a LAN (local area
network), Dijkstra’s algorithm can be used.
Consider that an infinite amount of time is required
for transmitting files from one computer to
another computer.
to minimize the number of “hops” from the file
server to every other computer on the network
the idea is to use Dijkstra’s algorithm to minimize
the shortest path between the networks resulting
in the minimum number of hops.
 Robotic Path

The drones/robots which are automated and are

used to deliver the packages to a specific
location or used for a task are loaded with this
algorithm module so that when the source and
destination is known,
the robot/drone moves in the ordered
direction by following the shortest path to
keep delivering the package in a minimum
amount of time.
Conclusion
 Dijkstra's algorithm is a graph search algorithm that solves the
single-source shortest path problem for a graph with non-negative
edge path costs, producing a shortest path tree.

if, d[u] + c(u,v) < d[v]

then, d[v] = d[u] + c(u,v)

The Advantages and Disadvantages of Dijkstra's Algorithm

The Differences between Prim's Algorithm, and Kruskal's Algorithm and,
Dijkstra's Algorithm.
Real life Applications of Dijkstra's Algorithm.
 Credits
21BCE11104 - Aditya Pawar (Introduction)
21BCE10761 - Abhishek Pokale (Phases of Dijkstra's Algorithm)
21BCE10799 - Kunal Vats (Problem 1)
21BCE10335 - Nilay Ashtekar (Problem 2)
21BCE11472 - Sanjay A.S. (Problem 3)
21BCE10762 - Akashvi (Advantages and Disadvantages)
21BCE10114 - Rohan Wetal (Prim's, Kruskal's & Dijkstra's)
21BCE10531 - Aditya Nair (Applications)
21BCE10995 - Evan T. Sinto (Conclusion)
*21BCE10653 - Jay Chawandke
Thank
you!!