Scribd
Upload
10 views

Dijkstras Algorithm

This lecture discusses Dijkstra's algorithm for finding the shortest path between nodes in a graph. It provides an overview of graphs and Dijkstra's algorithm, works through an example problem, and discusses applications and references for further reading.

Uploaded by

priyanshushawarn8183
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
10 views

Dijkstras Algorithm

This lecture discusses Dijkstra's algorithm for finding the shortest path between nodes in a graph. It provides an overview of graphs and Dijkstra's algorithm, works through an example problem, and discusses applications and references for further reading.

Uploaded by

priyanshushawarn8183
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 10

Lecture 3.2.

Dijkstra's algorithm

Course outcome to be covered:

CO3: Apply and recognized about the Graph Theory

1.1 Topic Objectives:

 To understand the concept of single source shortest path


problem.

 To compute the shortest path from one particular source node


to all other remaining nodes of the graph.

1.2 Introduction:

Dijkstra's algorithm, published in 1959, is named after its discoverer


Edsger Dijkstra, who was a Dutch computer scientist. This algorithm
aims to find the shortest-path in a directed or undirected graph with non-
negative edge weights.
Before, we look into the details of this algorithm , let’s have a quick
overview about the following:

 Graph: A graph is a non-linear data structure defined as G=(V,E)


where V is a finite set of vertices and E is a finite set of edges,
such that each edge is a line or arc connecting any two vertices.
 Weighted graph: It is a special type of graph in which every edge
is assigned a numerical value, called weight
 Connected graph: A path exists between each pair of vertices in
this type of graph
 Spanning tree for a graph G is a subgraph G’ including all the
vertices of G connected with minimum number of edges. Thus, for
a graph G with n vertices, spanning tree G’ will have n vertices and
maximum n-1 edges.

Conditions-

It is important to note the following points regarding Dijkstra


Algorithm-

 Dijkstra algorithm works only for connected graphs.


 Dijkstra algorithm works only for those graphs that do not contain any
negative weight edge.
 The actual Dijkstra algorithm does not output the shortest paths.
 It only provides the value or cost of the shortest paths.
 By making minor modifications in the actual algorithm, the shortest
paths can be easily obtained.
 Dijkstra algorithm works for directed as well as undirected graphs.

Dijkstra's algorithm

This algorithm maintains a set of vertices whose shortest paths from


source is already known. The graph is represented by its cost adjacency
matrix, where cost is the weight of the edge. In the cost adjacency matrix
of the graph, all the diagonal values are zero. If there is no path from
source vertex Vs to any other vertex Vi then it is represented by +∞.In
this algorithm, we have assumed all weights are positive.

1. Initially, there is no vertex in sets.


2. Include the source vertex Vs in S. Determine all the paths from
Vs to all other vertices without going through any other vertex.
3. Now, include that vertex in S which is nearest to V s and find the
shortest paths to all the vertices through this vertex and update the
values.
4. Repeat the step until n-1 vertices are not included in S if there are n
vertices in the graph.
After completion of the process, we got the shortest paths to all the
vertices from the source vertex.

Example:

Find the shortest paths between K and L in the graph shown in fig using
Dijkstra's Algorithm.

Solution:

Step1: Include the vertex K is S and determine all the direct paths from
K to all other vertices without going through any other vertex.

Distance to all other vertices


S K a b c d L

K 0 4(K) ∞ 2(K) ∞ 20(K)

Step2: 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.

Distance to all other vertices

S K a b c d L

K 0 3(K, c) 7(K, c) 2(K) 8(K, c) 18(K, c)

Step3: The vertex which is 2nd nearest to K is 9, included in S.

Distance to all other vertices

S K a b c d L

K 0 3(K, c) 7(K, c) 2(K) 7(K, c, a) 18(K,


c)

Step4: The vertex which is 3rd nearest to K is b, included in S.

Distance to all other vertices

S K a b c d L
K 0 3(K, c) 7(K, c) 2(K) 7(K, c, a) 8(K, c, b)

Step5: The vertex which is next nearest to K is d, is included in S.

Distance to all other vertices

S K a b c d L

K(c, a, b, 0 3(K, c) 7(K, c) 2(K) 7(K, c, a) 8(K, c,


d) b)

Since, n-1 vertices included in S.

Hence we have found the shortest distance from K to all other vertices.

Thus, the shortest distance between K and L is 8 and the shortest path is
K, c, b, L.

Some Areas of Application


 Used to determine the shortest path from one node in a graph
to every other node within the same graph (provided that the
nodes are reachable from the starting node).
 To find the maximum bandwidth path between two places in
the internet connection — Routers represents vertices and
Bandwidth represents vertices.
 Can be used in other Networking Algorithms and Routing
Protocols.
 It is particularly useful for Weighted Graphs and doesn’t work
for unweighted/negative-weighted graphs.
 Used in Telephone network.
 Used in Maps — Locations as vertices and Distances as edges.
 Path finding algorithms are heavily used in the transmission of
data over the internet/ network. The data comes from a far off
server to any device (IP address).
 This so called path, is a sequence of servers through which the
data must go through to finally end up on this device.
 The algorithms try to keep the path length as short as possible
to reduce transmission delay and cost, here again Dijkstra’s
algorithm works.

Practice Questions

FAQ

Q.1 What is the procedure to calculate the shortest path?

Ans: Dijkstra's algorithm can be used to determine the shortest


path from one node in a graph to every other node within the same
graph data structure, provided that the nodes are reachable from the
starting node. Dijkstra's algorithm can be used to find the shortest path
Q.2 Can Dijkstra find longest path?

Ans: The Dijkstra Algorithm is an algorithm that allows you to allocate


the shortest path in a graph between a starting node i and an end note j
by including other nodes of the graph. It can also be used to
calculate longest paths, if some simple modifications are used.

Summary

In this lecture, we have discussed about

 Dijkstra Algorithm
 Examples related to this Algorithm
 Different applications of Algorithm

REFERENCES

Books

[1] Elements of Discrete Mathematics, (Second Edition) C. L. Liu,


McGraw Hill, New Delhi, 2017

[2] G. Ronald, Knuth, Donald and Patashik Oren, concrete Mathematics:


A Foundation for Computer Science", Addison-Wesley.

Websites
[1] https://www.gatevidyalay.com/dijkstras-algorithm-shortest-path-
algorithm/
[2]https://www.tutorialspoint.com/design_and_analysis_of_algorithms/
design_and_analysis_of_algorithms_shortest_paths.htm

[3]https://brilliant.org/wiki/dijkstras-short-path-finder/

[4] https://www.javatpoint.com/discrete-mathematics-dijkstras-
algorithm

Courses

[1] https://www.coursera.org/specializations/discrete-mathematics

[2] https://www.classcentral.com/course/swayam-discrete-mathematics-
12929

Video Links

[1] https://youtu.be/lAXZGERcDf4

[2] https://www.youtube.com/watch?v=wt5cqvfdyxg

You might also like