Data Structure and Algorithm Lecture-04

Md. Sohag Hossain

Maintenance Engineer (Principal Officer)
Rajshahi Krishi Unnayan Bank (RAKUB)
1. Greedy Algorithm Kv‡K e‡j? `ywU Ggb mgm¨v eY©bv Kiæb hv Greedy Algorithm w`‡q
mgvavb Kiv hvq|6 (১৬ তম)

২। Greedy A¨vjMwi`g D`vniYmn e¨vL¨v Kiæb| 5 (১৬ তম)

What is Greedy Algorithm?

A greedy algorithm is a problem-solving technique that makes the best local choice
at each step in the hope of finding the global optimum solution. It prioritizes
immediate benefits over long-term consequences, making decisions based on the
current situation without considering future implications. While this approach can be
efficient and straightforward, it doesn’t guarantee the best overall outcome for all
problems.
However, it’s important to note that not all problems are suitable for greedy
algorithms. They work best when the problem exhibits the following properties:
 Greedy Choice Property: The optimal solution can be constructed by making
the best local choice at each step.
 Optimal Substructure: The optimal solution to the problem contains the
optimal solutions to its subproblems.

Characteristics of Greedy Algorithm

Here are the characteristics of a greedy algorithm:
 Greedy algorithms are simple and easy to implement.
 They are efficient in terms of time complexity, often providing quick solutions.
 Greedy algorithms are used for optimization problems where a locally
optimal choice leads to a globally optimal solution.
 These algorithms do not reconsider previous choices, as they make decisions
based on current information without looking ahead.
 Greedy algorithms are suitable for problems for optimal substructure.
These characteristics help to define the nature and usage of greedy algorithms in
problem-solving.
 Examples of Greedy Algorithm
Several well-known algorithms fall under the category of greedy algorithms. Here
are a few examples:
 Dijkstra’s Algorithm: This algorithm finds the shortest path between two nodes
in a graph. It works by repeatedly choosing the shortest edge available from the
current node.
 Kruskal’s Algorithm: This algorithm finds the minimum spanning tree of a
graph. It works by repeatedly choosing the edge with the minimum weight that
does not create a cycle.
 Fractional Knapsack Problem: This problem involves selecting items with the
highest value-to-weight ratio to fill a knapsack with a limited capacity. The
greedy algorithm selects items in decreasing order of their value-to-weight ratio
until the knapsack is full.
 Scheduling and Resource Allocation: The greedy algorithm can be used to
schedule jobs or allocate resources in an efficient manner.
 Coin Change Problem: The greedy algorithm can be used to make change for a
given amount with the minimum number of coins, by always choosing the coin
with the highest value that is less than the remaining amount to be changed.
 Huffman Coding: The greedy algorithm can be used to generate a prefix-free
code for data compression, by constructing a binary tree in a way that the
frequency of each character is taken into consideration.
Why to use Greedy Approach?
Here are some reasons why you might use the Greedy Approach:
 Simple and easy to understand: The Greedy Approach is straightforward and
easy to implement, making it a good choice for beginners.
 Fast and efficient: It usually finds a solution quickly, making it suitable for
problems where time is a constraint.
 Provides a good enough solution: While not always optimal, the Greedy
Approach often finds a solution that is close to the best possible solution.
 Can be used as a building block for other algorithms: The Greedy Approach
can be used as a starting point for developing more complex algorithms.
 Useful for a variety of problems: The Greedy Approach can be applied to a
wide range of optimization problems, including knapsack problems, scheduling
problems, and routing problems.

Greedy Algorithm
1. To begin with, the solution set (containing answers) is empty.
2. At each step, an item is added to the solution set until a solution is reached.

3. If the solution set is feasible, the current item is kept.

4. Else, the item is rejected and never considered again.

Example:
Let’s say you have a set of coins with values {1, 2, 5, 10, 20, 50, 100} and you need
to give minimum number of coin to someone change for 36.
The greedy algorithm for making change would work as follows:
1. Start with the largest coin value that is less than or equal to the amount to be
changed. In this case, the largest coin less than 36 is 20.
2. Subtract the largest coin value from the amount to be changed, and add the coin
to the solution. In this case, subtracting 20 from 36 gives 16, and we add
a 20 coin to the solution.
3. Repeat steps 1 and 2 until the amount to be changed becomes 0.
So, using the greedy algorithm, the solution for making change for 36 would be one
20 coins, one 10 coin, one 5 coins and one 1 coin needed.

২। Divide and Conquer technique Kx? `ywU mgm¨v eY©bv Kiæb hv Divide and Conquer
technique G mgavb Kiv hvq| (১৬ তম)
৪। Divide and Conquer GjMwi`g m¤c‡K© ms‡‣‡c wjLyb| 6 (১৩ তম)
৫। Divide and Conquer GjMwi`gwU e¨vL¨v Kiæb| 5 (১০ তম)

Divide and Conquer Algorithm


Divide and Conquer algorithm is a problem-solving strategy that involves
breaking down a complex problem into smaller, more manageable parts, solving
each part individually, and then combining the solutions to solve the original
problem. It is a widely used algorithmic technique in computer science and
mathematics.
Example: In the Merge Sort algorithm, the “Divide and Conquer” strategy is used
to sort a list of elements. Below image illustrate the dividing and merging states to
sort the array using Merge Sort.
Stages of Divide and Conquer Algorithm:
Divide and Conquer Algorithm can be divided into three
stages: Divide, Conquer and Merge.
1. Divide:
 Break down the original problem into smaller subproblems.
 Each subproblem should represent a part of the overall problem.
 The goal is to divide the problem until no further division is possible.
2. Conquer:
 Solve each of the smaller subproblems individually.
 If a subproblem is small enough (often referred to as the “base case”), we solve it
directly without further recursion.
 The goal is to find solutions for these subproblems independently.
3. Merge:
 Combine the sub-problems to get the final solution of the whole problem.
 Once the smaller subproblems are solved, we recursively combine their solutions
to get the solution of larger problem.
 The goal is to formulate a solution for the original problem by merging the results
from the subproblems.

Applications of Divide and Conquer Algorithm:

 Merge Sort: Merge sort is a classic example of a divide and conquer sorting
algorithm. It breaks down the array into smaller subarrays, sorts them individually,
and then merges them to obtain the sorted array.
 Median Finding: The median of a set of numbers can be found using a divide and
conquer approach. By recursively dividing the set into smaller subsets, the median
can be determined efficiently.
 Min and Max finding: Divide and Conquer algorithm can be used to find both the
minimum and maximum elements in an array simultaneously. By splitting the
array into halves and comparing the min-max pairs from each half, the overall min
and max can be identified in logarithmic time complexity.
 Matrix Multiplication: Strassen’s algorithm for matrix multiplication is a divide
and conquer technique that reduces the number of multiplications required for
large matrices by breaking down the matrices into smaller submatrices and
combining their products.
 Closest Pair problem: The closest pair problem involves finding the two closest
points in a set of points in a multidimensional space. A divide and conquer
algorithm, such as the “divide and conquer closest pair” algorithm, can efficiently
solve this problem by recursively dividing the points and merging the solutions
from the subproblems.

ডিভাইি-এন্ড-কনকার

মার্জ সর্ জ এবং কুইকসর্ জ এই দুইটি অ্যালগ াডরদমই পুনরাবৃডির উপগর ডভডি কগর সাধারণ একটি
অ্যালগ াডরদডমক উদাহরণ ডনযুক্ত কগর থাগক। এই ডিভাইি এন্ড কনকার উদাহরণটি, একটি সমস্যাগক
ছ ার্ ছ ার্ সমস্যাগত ডবভক্ত কগর ছেগল ছেগুগলা মূল সমস্যার অ্নুরূপ, পুনরাবৃডির মাধ্যগম কার্ কগর এই
ছ ার্ সমস্যাগুগলা সমাধান কগর থাগক এবং সবগেগে এই ছ ার্ সমস্যাগুগলার সমাধান একসাগথ করার
 মাধ্যগম মূল সমস্যাটি সমাধান করা হয়। কারণ ডিভাইি এন্ড কনকার এই ছ ার্ সমস্যাগুগলা পুনরাবৃডির
মাধ্যগম সমাধান কগর থাগক, প্রডতটি ছ ার্ সমস্যা অ্বশ্যই মূল সমস্যাটি ছথগক ছ ার্ হগত হগব এবং ছ ার্
সমস্যাগুগলার র্ন্য অ্বশ্যই একটি ডভডি থাকগত হগব। আমাগদর এখাগন মগন রাখা দরকার ডিভাইি এন্ড
কনকার অ্যালগ াডরদগমর ডতনটি অ্ংে রগয়গ :

1. ডবভডক্ত: মূল সমস্যাটি কতগুগলা ছ ার্ ছ ার্ সমস্যাগত ডবভক্ত কগর ছেলগত হগব ছের্া হগব একই মূল
সমস্যার ছ ার্ রূপ।
2. র্য়: ছ ার্ সমস্যাগুগলা পুনরাবৃডি ব্যবহার করার মাধ্যগম সমাধান করা োয়। েডদ তারা ছবে ছ ার্
আকাগরর সমস্যা হয়, তাহগল এই ছ ার্ সমস্যাগুগলা ছবস ছকস ডহগসগব সমাধান করা োয়।
3. একত্রীকরণ: ছ ার্ সমস্যার সমাধানগুগলা সংযুক্ত করগল মূল সমস্যার সমাধান হগয় োগব।

Greedy Method Vs Dynamic Programming

Greedy Method Dynamic Programming

A single sequence of the decision is Various numbers of sequences of the
generated. decision are generated.
Not as reliable as Dynamic
very reliable.
programming.
Follows bottom-up or top-down
Follows serial forward approach.
approach.
An optimal solution may not be The optimal solution is achieved every
achieved. time.
Locally optimal choices are made on Uses already produced solutions of the
each step. previous steps to
Memory consumed more than the Greedy
Memory efficient.
method.
Quicker results. Slower results comparatively.
Example: Fractional knapsack problem. Example: 0/1 knapsack problem.

Greedy Algorithm vs Divide and Conquer Algorithm vs Dynamic Algorithm

[Link] Greedy Algorithm Divide and conquer Dynamic Programming

Follows Top-down
1 Follows Top-down approach Follows bottom-up approach
approach

Used to solve optimization Used to solve decision Used to solve optimization

2
problem problem problem

The optimal solution is generated

Solution of subproblem is The solution of subproblems is
without revisiting previously
3 computed recursively more computed once and stored in a
generated solutions; thus, it
than once. table for later use.
avoids the re-computation

It is used to obtain a
It may or may not generate an solution to the given It always generates optimal
4
optimal solution. problem, it does not aim solution.
for the optimal solution

5 Iterative in nature. Recursive in nature. Recursive in nature.

efficient and fast than divide more efficient but slower than
and conquer. For instance, greedy. For instance, single
6 single source shortest path less efficient and slower. source shortest path finding
finding using Dijkstra’s Algo using Bellman Ford Algo takes
takes O(ElogV) time O(VE) time.

more memory is required to store

7 extra memory is not required. some memory is required.
subproblems for later use.
 Examples: Fractional Knapsack Examples: Merge sort,
Examples: 0/1 Knapsack,
problem, Quick sort,
8 All pair shortest path,
Activity selection problem, Strassen’s matrix
Matrix-chain multiplication.
Job sequencing problem. multiplication.

৬। Hashing ej‡Z Kx eySvq? Hash dvskb MV‡bi R‡b¨ †h †Kv‡bv wZbwU c×wZ wjLyb| (১৫ তম)

Hash Functions and list/types of Hash functions

Hashing is the process of generating a value from a text or a list of numbers using a
mathematical function known as a hash function.

A Hash Function is a function that converts a given numeric or alphanumeric key to a

small practical integer value. The mapped integer value is used as an index in the hash
table. In simple terms, a hash function maps a significant number or string to a small
integer that can be used as the index in the hash table.

The pair is of the form (key, value), where for a given key, one can find a value using
some kind of a “function” that maps keys to values. The key for a given object can be
calculated using a function called a hash function. For example, given an array A, if i
is the key, then we can find the value by simply looking up A[i].

Types of Hash functions

There are many hash functions that use numeric or alphanumeric keys. This article
focuses on discussing different hash functions:

1. Division Method.

2. Mid Square Method.

3. Folding Method.

4. Multiplication Method.

Let’s begin discussing these methods in detail.

1. Division Method:

This is the most simple and easiest method to generate a hash value. The hash function
divides the value k by M and then uses the remainder obtained.
Formula:

h(K) = k mod M

Here, k is the key value, and M is the size of the hash table.

It is best suited that M is a prime number as that can make sure the keys are more
uniformly distributed. The hash function is dependent upon the remainder of a division.

Example:

k = 12345 M = 95 h(12345) = 12345 mod 95 = 90

k = 1276 M = 11 h(1276) = 1276 mod 11 = 0

Pros:

1. This method is quite good for any value of M.

2. The division method is very fast since it requires only a single division operation.

Cons:

1. This method leads to poor performance since consecutive keys map to consecutive
hash values in the hash table.

2. Sometimes extra care should be taken to choose the value of M.

2. Mid Square Method:

The mid-square method is a very good hashing method. It involves two steps to compute
the hash value-

1. Square the value of the key k i.e. k2

2. Extract the middle r digits as the hash value.

Formula:

h(K) = h(k x k)

Here, k is the key value.

The value of r can be decided based on the size of the table.

Example:

Suppose the hash table has 100 memory locations. So r = 2 because two digits are
required to map the key to the memory location.

k = 60 k x k = 60 x 60 = 3600 h(60) = 60

The hash value obtained is 60

Pros:

1. The performance of this method is good as most or all digits of the key value
contribute to the result. This is because all digits in the key contribute to generating the
middle digits of the squared result.

2. The result is not dominated by the distribution of the top digit or bottom digit of the
original key value.

Cons:

1. The size of the key is one of the limitations of this method, as the key is of big size
then its square will double the number of digits.

2. Another disadvantage is that there will be collisions but we can try to reduce
collisions.

3. Digit Folding Method:

This method involves two steps:

1. Divide the key-value k into a number of parts i.e. k1, k2, k3,….,kn, where each part
has the same number of digits except for the last part that can have lesser digits than the
other parts.

2. Add the individual parts. The hash value is obtained by ignoring the last carry if any.

Formula:

k = k1, k2, k3, k4, ….., kn s = k1+ k2 + k3 + k4 +….+ kn h(K)= s

Here, s is obtained by adding the parts of the key k

Example:
k = 12345 k1 = 12, k2 = 34, k3 = 5 s = k1 + k2 + k3 = 12 + 34 + 5
= 51 h(K) = 51

Note: The number of digits in each part varies depending upon the size of the hash
table. Suppose for example the size of the hash table is 100, then each part must have
two digits except for the last part which can have a lesser number of digits.

4. Multiplication Method

This method involves the following steps:

1. Choose a constant value A such that 0 < A < 1.

2. Multiply the key value with A.

3. Extract the fractional part of kA.

4. Multiply the result of the above step by the size of the hash table i.e. M.

5. The resulting hash value is obtained by taking the floor of the result obtained in
step 4.

Formula:

h(K) = floor (M (kA mod 1))

Here, M is the size of the hash table. k is the key value. A is a constant value.

Example:

k = 12345 A = 0.357840 M = 100

h(12345) = floor[ 100 (12345*0.357840 mod 1)] = floor[ 100 (4417.5348 mod 1) ] =
floor[ 100 (0.5348) ] = floor[ 53.48 ] = 53

Pros:

The advantage of the multiplication method is that it can work with any value between
0 and 1, although there are some values that tend to give better results than the rest.

Cons:

The multiplication method is generally suitable when the table size is the power of
two, then the whole process of computing the index by the key using multiplication
hashing is very fast.
What is a Minimum Spanning Tree?
• A minimum spanning tree (MST) is a subset of the edges of a connected, edge-
weighted graph that connects all the vertices together without any cycles and
with the minimum possible total edge weight.

• It is a way of finding the most economical way to connect a set of vertices.

Minimum Spanning-Tree Algorithm

• We shall learn about two most important spanning tree algorithms here −

 Kruskal's Algorithm
 Prim's Algorithm
• Both are greedy algorithms.

Prim’s Algorithm for Minimum Spanning Tree (MST)

How does Prim’s Algorithm Work?
The working of Prim’s algorithm can be described by using the following steps:
Step 1: Determine an arbitrary vertex as the starting vertex of the MST.
Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST
(known as fringe vertex).
Step 3: Find edges connecting any tree vertex with the fringe vertices.
Step 4: Find the minimum among these edges.
Step 5: Add the chosen edge to the MST if it does not form any cycle.
Step 6: Return the MST and exit

Illustration of Prim’s Algorithm:

Consider the following graph as an example for which we need to find the
Minimum Spanning Tree (MST).
 Example of a graph

Step 1: Firstly, we select an arbitrary vertex that acts as the starting vertex of
the Minimum Spanning Tree. Here we have selected vertex 0 as the starting
vertex.

0 is selected as starting vertex

Step 2: All the edges connecting the incomplete MST and other vertices are the
edges {0, 1} and {0, 7}. Between these two the edge with minimum weight is {0,
1}. So include the edge and vertex 1 in the MST.
 1 is added to the MST

Step 3: The edges connecting the incomplete MST to other vertices are {0, 7},
{1, 7} and {1, 2}. Among these edges the minimum weight is 8 which is of the
edges {0, 7} and {1, 2}. Let us here include the edge {0, 7} and the vertex 7 in
the MST. [We could have also included edge {1, 2} and vertex 2 in the MST].

7 is added in the MST

Step 4: The edges that connect the incomplete MST with the fringe vertices are
{1, 2}, {7, 6} and {7, 8}. Add the edge {7, 6} and the vertex 6 in the MST as it
has the least weight (i.e., 1).
 6 is added in the MST

Step 5: The connecting edges now are {7, 8}, {1, 2}, {6, 8} and {6, 5}. Include
edge {6, 5} and vertex 5 in the MST as the edge has the minimum weight (i.e.,
2) among them.

Include vertex 5 in the MST

Step 6: Among the current connecting edges, the edge {5, 2} has the minimum
weight. So include that edge and the vertex 2 in the MST.
 Include vertex 2 in the MST

Step 7: The connecting edges between the incomplete MST and the other
edges are {2, 8}, {2, 3}, {5, 3} and {5, 4}. The edge with minimum weight is edge
{2, 8} which has weight 2. So include this edge and the vertex 8 in the MST.

Add vertex 8 in the MST

Step 8: See here that the edges {7, 8} and {2, 3} both have same weight which
are minimum. But 7 is already part of MST. So we will consider the edge {2, 3}
and include that edge and vertex 3 in the MST.
 Include vertex 3 in MST

Step 9: Only the vertex 4 remains to be included. The minimum weighted edge
from the incomplete MST to 4 is {3, 4}.

Include vertex 4 in the MST

The final structure of the MST is as follows and the weight of the edges of the
MST is (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37.
 The structure of the MST formed using the above method

Note: If we had selected the edge {1, 2} in the third step then the MST would
look like the following.

Structure of the alternate MST if we had selected edge {1, 2} in the MST

1. †`Lvb †h, n msL¨K Vertex Gi GKwU tree Gi wVK n-1 msL¨K edge Av‡Q| 4
Kruskal’s Minimum Spanning Tree (MST) Algorithm
In Kruskal’s algorithm, sort all edges of the given graph in increasing order. Then it keeps on
adding new edges and nodes in the MST if the newly added edge does not form a cycle. It picks
the minimum weighted edge at first and the maximum weighted edge at last. Thus we can say
that it makes a locally optimal choice in each step in order to find the optimal solution. Hence
this is a Greedy Algorithm.
How to find MST using Kruskal’s algorithm?
Below are the steps for finding MST using Kruskal’s algorithm:
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so
far. If the cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

Illustration:
Below is the illustration of the above approach:
Input Graph:

The graph contains 9 vertices and 14 edges. So, the minimum spanning tree
formed will be having (9 – 1) = 8 edges.
After sorting:

Weight Source Destination

1 7 6

2 8 2

2 6 5

4 0 1

4 2 5
 Weight Source Destination

6 8 6

7 2 3

7 7 8

8 0 7

8 1 2

9 3 4

10 5 4

11 1 7

14 3 5

Now pick all edges one by one from the sorted list of edges
Step 1: Pick edge 7-6. No cycle is formed, include it.

Add edge 7-6 in the MST

Step 2: Pick edge 8-2. No cycle is formed, include it.

Add edge 8-2 in the MST

Step 3: Pick edge 6-5. No cycle is formed, include it.

Add edge 6-5 in the MST

Step 4: Pick edge 0-1. No cycle is formed, include it.

Add edge 0-1 in the MST

Step 5: Pick edge 2-5. No cycle is formed, include it.

 Add edge 2-5 in the MST

Step 6: Pick edge 8-6. Since including this edge results in the cycle, discard
it. Pick edge 2-3: No cycle is formed, include it.

Add edge 2-3 in the MST

Step 7: Pick edge 7-8. Since including this edge results in the cycle, discard
it. Pick edge 0-7. No cycle is formed, include it.
 Add edge 0-7 in MST

Step 8: Pick edge 1-2. Since including this edge results in the cycle, discard
it. Pick edge 3-4. No cycle is formed, include it.

Add edge 3-4 in the MST

Note: Since the number of edges included in the MST equals to (V – 1), so the
algorithm stops here
Shortest Paths from Source to all Vertices using Dijkstra’s Algorithm
Given a graph and a source vertex in the graph, find the shortest paths from the source
to all vertices in the given graph.
Examples:
Input: src = 0, the graph is shown below.

Output: 0 4 12 19 21 11 9 8 14
Explanation: The distance from 0 to 1 = 4.
The minimum distance from 0 to 2 = 12. 0->1->2
The minimum distance from 0 to 3 = 19. 0->1->2->3
The minimum distance from 0 to 4 = 21. 0->7->6->5->4
The minimum distance from 0 to 5 = 11. 0->7->6->5
The minimum distance from 0 to 6 = 9. 0->7->6
The minimum distance from 0 to 7 = 8. 0->7
The minimum distance from 0 to 8 = 14. 0->1->2->8

Dijkstra shortest path algorithm for Adjacency Matrix in O(V 2):

The idea is to generate a SPT (shortest path tree) with a given source as a root.
Maintain an Adjacency Matrix with two sets,
 one set contains vertices included in the shortest-path tree,
 other set includes vertices not yet included in the shortest-path tree.
At every step of the algorithm, find a vertex that is in the other set (set not yet included)
and has a minimum distance from the source.
Follow the steps below to solve the problem:
 Create a set sptSet (shortest path tree set) that keeps track of vertices included in the
shortest path tree, i.e., whose minimum distance from the source is calculated and
finalized. Initially, this set is empty.
 Assign a distance value to all vertices in the input graph. Initialize all distance
values as INFINITE. Assign the distance value as 0 for the source vertex so that it
is picked first.
 While sptSet doesn’t include all vertices
 Pick a vertex u that is not there in sptSet and has a minimum distance
value.
 Include u to sptSet.
 Then update the distance value of all adjacent vertices of u.
 To update the distance values, iterate through all adjacent
vertices.
 For every adjacent vertex v, if the sum of the distance value of u
(from source) and weight of edge u-v, is less than the distance
value of v, then update the distance value of v.
Note: We use a boolean array sptSet[] to represent the set of vertices included in SPT.
If a value sptSet[v] is true, then vertex v is included in SPT, otherwise not. Array dist[]
is used to store the shortest distance values of all vertices.
Below is the illustration of the above approach:
Illustration:
To understand the Dijkstra’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).