Dijkstra Algorithm
By BYJU'S Exam Prep
Updated on: September 25th, 2023
Dijkstra Algorithm is used to determine the shortest path between two nodes in a graph. In particular, you may create a shortestpath tree by determining the shortest path from a node (referred to as the “source node”) to every other node in the graph.
To determine the shortest path between the present location and the destination, GPS devices employ Dijkstra Algorithm. It has several industrial uses, particularly in fields where modeling networks are necessary.
Also see – GATE 2023 Rank Predictor Tool
Table of content
What is the Dijkstra Algorithm?
The singlesource shortest path issue for a directed graph G = (V, E) with nonnegative edge weights is solved by the greedy algorithm known as the Dijkstra algorithm, which bears the name of its discoverer, Dutch computer scientist Edsger Dijkstra. In other words, we suppose that for any edge (u, v) є E, w(u, v) ≥ 0.
The Dijkstra algorithm maintains a collection of S vertices with predetermined final shortestpath weights from the source. The procedure continually chooses the vertex u є VS with the least shortest path estimate, inserts u into S, and relaxes all edges leaving u. In other words, all vertices in S have d[v] = 8(s, v). All the vertices in VS are kept in a minpriority queue Q that is keyed by their d values. Adjacency lists are used to represent Graph G.
Pseudocode of Dijkstra Algorithm
Every vertex’s route distance must be preserved. That can be kept in a vdimensional array, where v is the total number of vertices. Not only do we want to know how long the shortest path is, but we also want to be able to find it. Each vertex is mapped to the vertex that most recently changed its path length for this purpose.
When the process is finished, we can move backward to find the path by going from the source vertex to the destination vertex. The vertex with the shortest path distance can be efficiently received using a minimal priority queue.
The pseudocode of Dijkstra algorithm is as follows:
DIJKSTRA (G, w, s)
INITIALIZESINGLESOURCE (G, s)
S ← Ø
Q ← V[G]
while Q ≠ Ø
do u ← EXTRACTMIN (Q)
S ← S ∪ (u)
for each vertex v є Adj[u]
do RELAX (u, v, w)
Analysis of Dijkstra Algorithm
The BigO notation can be used to define the running time of the Dijkstra algorithm as a function of E and V on a graph with edges and vertices. The Dijkstra algorithm can be implemented in several ways. Still, its basic form stores Q’s vertices in an ordinary linked list or array, and operation ExtractMin (Q) is just a linear search through all of Q’s vertices. The running time in this context is O(V^{2}+ E) = O(V^{2}).
Dijkstra algorithm can be implemented more effectively for sparse graphs, or graphs with much fewer edges than V^{2}, by storing the graph as adjacency lists and utilizing a binary heap or Fibonacci heap as the priority queue to implement the ExtractMin function. When using a binary heap, the algorithm takes O(( E V) time, which is dominated by O(E log V) when every vertex is assumed to be connected. The Fibonacci heap reduces this time to O(E + V log V]).
Example of Dijkstra Algorithm
Consider the directed graph:
Find the shortest path from the source vertex A to the other vertices using the Dijkstra algorithm.
Solution:
Dijkstra algorithm maintains a group of S of vertices whose final shortestpath weights from the source have already been determined. The Dijkstra algorithm repeatedly selects the vertex u є VS with the minimum shortestpath estimate, inserts u into S, and relaxes all edges leaving u. We maintain a minpriority queue Q that contains all the vertices in V – S keyed by their d values.
Initialize:
‘A’ ← EXTRACTMIN (Q):
Relax all edges Leaving ‘A’ S: {A}
‘C’ ← EXTRACTMIN(Q):
Relax all edges Leaving ‘A’ S: {A, C}
‘E’ ← EXTRACTMIN (Q):
Relax all edges Leaving ‘A’ S: {A, C, E}
‘B’ ← EXTRACTMIN (Q):
Relax all, Leaving’ A’ S: {A, C, E, B}
‘D’ ← EXTRACTMIN (Q):
S: {A, C, E, B, D}
GATE Computer Science Engineering Revision Sheet and Formulae
Check – Click Here to check your GATE 2023 Rank Predictor Tool
Important GATE Topics 

Fixed End Moment  Gravity Of Earth 
Slope Deflection Equation  Capacitors in Parallel 
Capacitors in Series  Carnot Cycle 
Cement Test  Clamping Circuit 
CMOS Converter  Column Base 