1.

DIJKSTA’S ALGORITHM

Dijkstra's algorithm is a fundamental graph algorithm used to find the shortest path from a starting node
to all other nodes in a graph with non-negative edge weights. This algorithm, named after Dutch
computer scientist EdsgerDijkstra, has significant applications in various domains such as network
routing, transportation systems, and GPS navigation. In this comprehensive explanation, we will delve
into the intricacies of Dijkstra's algorithm, its implementation, optimization techniques, practical
applications, and limitations.

Introduction to Dijkstra's Algorithm

Graphs are widely used to model relationships between entities, where nodes represent entities, and
edges represent connections or relationships between them. In a graph, each edge may have a weight
associated with it, signifying the cost or distance between connected nodes. Dijkstra's algorithm
efficiently determines the shortest path from a single source node to all other nodes in a graph with
non-negative edge weights.

Algorithm Description
Initialization: The algorithm begins by setting the distance to the source node as 0 and all other nodes'
distances as infinity. It uses a priority queue to keep track of nodes based on their current distances.
Greedy Approach: At each iteration, Dijkstra's algorithm selects the node with the smallest distance
from the priority queue. This node is considered 'visited,' and its neighboring nodes are relaxed to
update their distances if a shorter path is found.

Relaxation Step: For each neighboring node of the current node, the algorithm updates the distance if
the sum of the current node's distance and the edge weight connecting them is less than the previous
distance to the neighbor.

Optimality:Dijkstra's algorithm maintains the invariant that once a node is visited, its shortest distance
is determined, ensuring optimality in the calculated distances.

theDijkstra’s Algorithm lets take a graph and find the shortest path from source to all nodes.

Consider below graph and src = 0

Step 1:
 The set sptSet is initially empty and distances assigned to vertices are {0, INF, INF, INF, INF,
INF, INF, INF} where INF indicates infinite.

 Now pick the vertex with a minimum distance value. The vertex 0 is picked, include it
in sptSet. So sptSet becomes {0}. After including 0 to sptSet, update distance values of its
adjacent vertices.
 Adjacent vertices of 0 are 1 and 7. The distance values of 1 and 7 are updated as 4 and 8.
The following subgraph shows vertices and their distance values, only the vertices with finite
distance values are shown. The vertices included in SPT are shown in green colour.

Step 2:
 Pick the vertex with minimum distance value and not already included in SPT (not
in sptSET). The vertex 1 is picked and added to sptSet.
 So sptSet now becomes {0, 1}. Update the distance values of adjacent vertices of 1.
 The distance value of vertex 2 becomes 12.
Step 3:
 Pick the vertex with minimum distance value and not already included in SPT (not
in sptSET). Vertex 7 is picked. So sptSet now becomes {0, 1, 7}.
 Update the distance values of adjacent vertices of 7. The distance value of vertex 6
and 8 becomes finite (15 and 9 respectively).

Step 4:
 Pick the vertex with minimum distance value and not already included in SPT (not
in sptSET). Vertex 6 is picked. So sptSet now becomes {0, 1, 7, 6}.
 Update the distance values of adjacent vertices of 6. The distance value of vertex 5
and 8 are updated.

We repeat the above steps until sptSet includes all vertices of the given graph. Finally,
we get the following Shortest Path Tree (SPT).
2. RSA ALGORITHM

The RSA algorithm, named after its inventors Rivest, Shamir, and Adleman, is a widely
used encryption algorithm in the field of cryptography. It is based on the mathematical
properties of large prime numbers and their factorization. The algorithm involves
generating a public and private key pair, where the public key is used for encryption
and the private key is used for decryption.

In terms of time complexity, the RSA algorithm relies on the difficulty of factoring large
numbers into their prime factors. The key operation in RSA encryption and decryption is
modular exponentiation, which has a time complexity of O(log n) using the square-and-
multiply algorithm. The overall time complexity of the RSA algorithm is influenced by
the size of the keys used, with larger key sizes leading to increased computational
complexity.

Asymptotic notation, such as Big O notation, is commonly used in the design and
analysis of algorithms like RSA to describe their time complexity in terms of the input
size. It provides a way to analyze the efficiency of algorithms and compare their
performance as the input size grows. In the case of RSA, asymptotic notation helps in
understanding how the algorithm scales with larger key sizes and input data.
Recurrence equations can also play a role in analyzing the time complexity of
algorithms like RSA, particularly when considering the recursive nature of certain
operations. By defining and solving recurrence equations, it is possible to derive
insights into the computational complexity of algorithms and make informed decisions
about their efficiency and scalability.