Khulna University of Engineering & Technology
KUET
SESSIONAL REPORT
Course No: CSE 2202
Department Of Computer Science and Engineering
Experiment No: 01
Name of the Experiment: Implementation and Analysis of Dijkstra’s Algorithm
Remarks
Name : [Link] ISLAM
Roll No. : 2207078
Group No. : B1
Date of Performance : 09/10/2025 Year : 2nd
Date of Submission : : 23/10/2025 Term : 2nd
Objectives:
To learn how to find shortest path from a weighted graph
To understand Dijkstra’s Algorithm
To Implement Dijkstra’s algorithm in C++ using priority queue or set
To analysis the time complexity of Dijkstra’s algorithm
Introduction:
The dijkstra’s algorithm is designed to find the shortest path between two
vertices of a graph. These two vertices could either be adjacent or the farthest
points in the graph. The algorithm starts from the source. The inputs taken by
the algorithm are the graph G {V, E}, where V is the set of vertices and E is the
set of edges, and the source vertex S. And the output is the shortest path
spanning tree. Since the shortest path can be calculated from single source
vertex to all the other vertices in the graph, Dijkstra’s algorithm is also
called single-source shortest path algorithm. Dijkstra's algorithm has many
variants but the most common one is to find the shortest paths from the
source vertex to all other vertices in the graph.
Algorithm Steps:
Set all vertices distances = infinity except for the source vertex, set the
source distance =0.
Push the source vertex in a min-priority queue in the form (distance,
vertex), as the comparison in the min-priority queue will be according to
vertices distances.
Pop the vertex with the minimum distance from the priority queue (at
first the popped vertex = source).
Update the distances of the connected vertices to the popped vertex in
case of "current vertex distance + edge weight < next vertex distance",
then push the vertex
with the new distance to the priority queue.
If the popped vertex is visited before, just continue without using it.
Apply the same algorithm again until the priority queue is empty.
Code section:
We use the “dis” array to store each node’s distance from the source, and the
visited array to make sure a node isn’t processed more than once. We use a
min-heap (priority queue) to implement Dijkstra’s algorithm. To find the
shortest paths, we pop the closest node from the heap and apply the
relaxation formula to each of its adjacent nodes, updating their distances if we
find a shorter route.
Complexity analysis
The code runs Dijkstra on a graph with n nodes and m edges using an
adjacency list and a min-heap, so the running time is about O((n + m) · log n)
each edge is relaxed a constant number of times and each heap push/pop
costs O(log n)
Space usage is O(n + m) for the adjacency list plus O(n) for the dis and visited
arrays.
Time complexity : O((n+m).log n)
Space complexity : O(n+m)
Discussion and Conclusion:
In this lab we implement Dijkstra’s algorithm using an adjacency list, a dis array
to hold each node’s distance from the source, and a visited array so we don’t
visit the same node more than once. We use a min-heap (priority queue) to
always pick the closest unvisited node, and the key step is the relaxation
dis[current] + w < dis[neighbor] which updates a neighbor’s distance when we
find a shorter path. The program prints shortest distances from the source
(unreachable nodes keep their “infinite” value). Using a priority queue has
clear benefits, it is simple to code, use the heap to always work on the smallest
weight node first, and is much faster for sparse graphs than the basic O(n^2)
approach — the usual running time is about O((n + m)·log n).
References:
Lecture slide
[Link]
dijkstras_shortest_path_algorithm.htm
[Link]
path-algorithms/tutorial/
[Link]
dijkstras-algorithm/