Dijkstra's Algorithm
DR. SHWETA SHARMA
Dijkstra's Algorithm
It is used to find the shortest path between a node/vertex (source node)
to any (or every) other nodes/vertices (destination nodes) in a graph
A graph is basically an interconnection of nodes connected by edges
This algorithm is sometimes referred to as Single Source Shortest Path
Algorithm due to its nature of implementation
It can also be used for finding the shortest path from a starting node to
all other nodes in a graph i.e., given a source vertex, it finds shortest path
from source to all other vertices
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 2
Dijkstra's Algorithm
Dijkstra's algorithm allows us to find the shortest path between any two
vertices of a graph
Dijkstra's Algorithm works on the basis that any subpath B -> D of the
shortest path A -> D between vertices A and D is also the shortest path
between vertices B and D
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.
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 3
Dijkstra's Algorithm
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 4
Example of Dijkstra's Algorithm
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 5
Example of Dijkstra's Algorithm
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 6
Example of Dijkstra's Algorithm
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 7
Example of Dijkstra's Algorithm
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 8
Example of Dijkstra's Algorithm
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 9
Example of Dijkstra's Algorithm
After each iteration,
we pick the unvisited
vertex with the least
path length. So we
choose 5 before 7
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 10
Example of Dijkstra's Algorithm
7+2>8
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 11
Example of Dijkstra's Algorithm
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 12
Question 1
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 13
Solution 1
Output: 0 4 12 19 21 11 9 8 14
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 14
Question 3
Cost form A to D is _________________
Cost form A to E is _________________
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 15
Solution 3
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 16
Question4
Step through Dijkstra’s algorithm to calculate the single-source shortest paths from A to every other
vertex. Indicate the lowest-cost path from node A to node F
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 17
Solution 4
Step through Dijkstra’s algorithm to calculate the single-source shortest paths from A to every other
vertex. Indicate the lowest-cost path from node A to node F
A B C G E D or F D or F
Lowest-cost path from A to F: A to B to C to E to F
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 18
Drawbacks of Dijkstra’s algorithm
Dijkstra’s algorithm is not well-suited for finding shortest paths in a
graph with negative edge weights
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 19
Thank you!
DR. SHWETA SHARMA, DEPT. OF CSE, PEC CHANDIGARH 20
