Greedy Algorithms

The greedy method is one of the strategies like Divide and conquer used

to solve the problems.

This method is used for solving optimization problems.
An optimization problem is a problem that demands either maximum or
minimum results.
The Greedy method is the simplest and straightforward approach.
It is not an algorithm, but it is a technique.
It is used in finding the shortest path.

Components of Greedy Algorithm

A candidate set − A solution is created from this set.
A selection function − Used to choose the best candidate to be added
to the solution.
A feasibility function − Used to determine whether a candidate can be
used to contribute to the solution.
An objective function − Used to assign a value to a solution or a partial
solution.
A solution function − Used to indicate whether a complete solution has
been reached.

Drawback of Greedy Approach

The greedy algorithm doesn't always produce the optimal solution. This

is the major disadvantage of the algorithm

F or example, suppose we want to find the longest path in the graph below

from root to leaf. Let's use the greedy algorithm here.

e
M
ov

h
Our problem is to find the largest path. And, the optimal solution at the

moment is 3. So, the greedy algorithm will choose 3.

c
Finally the weight of an only child of 3 is 1. This gives us our final result

e
20 + 3 + 1 = 24.

T
However, it is not the optimal solution. There is another path that carries
more weight (20 + 2 + 10 = 32).

Spanning Tree
A spanning tree is a subset of an undirected Graph that has all the vertices
connected by minimum number of edges.
If all the vertices are connected in a graph, then there exists at least one
spanning tree. In a graph, there may exist more than one spanning tree.

Properties:
A spanning tree does not have any cycle.
Any vertex can be reached from any other vertex.

Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subset of edges of a connected
weighted undirected graph that connects all the vertices together with
the minimum possible total edge weight.
To derive an MST, Prim’s algorithm or Kruskal’s algorithm can be used.

Prim’s Algorithm
P rim’s Algorithm is a famous greedy algorithm.
It is used for finding the Minimum Spanning Tree (MST) of a given graph.
To apply Prim’s algorithm, the given graph must be weighted, connected
and undirected.

Prim’s Algorithm Implementation

Step-01:

Randomly choose any vertex.

e
The vertex connecting to the edge having least weight is usually
selected.
Step-02:

o
ind all the edges that connect the tree to new vertices.

v
F
Find the least weight edge among those edges and include it in the
existing tree.
If including that edge creates a cycle, then reject that edge and look for
the next least weight edge.

M
h
Step-03:

c
Keep repeating step-02 until all the vertices are included and Minimum
Spanning Tree (MST) is obtained.

C
e
PRACTICE PROBLEMS BASED ON PRIM’S ALGORITHM

T
onstruct the minimum spanning tree (MST) for the given graph using

Prim’s Algorithm-

Solution: The above discussed steps are followed

S tep:1

S tep:2

S tep:3

S tep:4

S tep:5

S tep:6

e
S

ince all the vertices have been included in the MST, so we stop.

Now, Cost of Minimum Spanning Tree

um of all edge weights

M
ov

h
=S

5 + 22 + 12 + 16 + 14

c
= 10 + 2

e
= 99 units

T
Time Complexities
Worst case time complexity of Prim’s Algorithm is-

ElogV) using binary heap

O(
O(E + VlogV) using Fibonacci heap

If adjacency list is used to represent the graph, then using breadth first search,

all the vertices can be traversed in O(V + E) time.

Min heap operations like extracting minimum element and decreasing key

value takes O(logV) time.

So, overall time complexity

= O( E + V) x O(logV)

= O(( E + V)logV)

= O( ElogV)

PRACTICE PROBLEMS BASED ON PRIM’S ALGORITHM

Using Prim’s Algorithm, find the cost of minimum spanning tree (MST) of the

given graph-

Solution:

Now, Cost of Minimum Spanning Tree

=S um of all edge weights

=1+4+2+ 6 + 3 + 10

=2 6 units

Kruskal’s Algorithm
K ruskal’s Algorithm is a famous greedy algorithm.
It is used for finding the Minimum Spanning Tree (MST) of a given graph.
To apply Kruskal’s Algorithm, the given graph must be weighted,
connected and undirected.

Kruskal’s Algorithm Implementation

S tep-01:

e
ov
S ort all the edges from low weight to high weight.
S tep-02:

Take the edge with the lowest weight and use it to connect the vertices

M
of graph.

h
If adding an edge creates a cycle, then reject that edge and go for the
next least weight edge.

c
S tep-03:

e
Keep adding edges until all the vertices are connected and a Minimum

T
Spanning Tree (MST) is obtained.

PRACTICE PROBLEMS BASED ON KRUSKAL’s ALGORITHM

Construct the minimum spanning tree (MST) for the given graph using

Kruskal’s Algorithm-

Solution: To construct MST using Kruskal’s Algorithm,

Simply draw all the vertices on the paper.

Connect these vertices using edges with minimum weights such that no

cycle gets formed.

Step:1

Step:2

Step:3

Step:4

e
M
ov
Step:5

ch
Te
Step:6

Step:7

S ince all the vertices have been connected / included in the MST, so we stop.

Weight of the MST

=S um of all edge weights

= 10 + 2 5 + 22 + 12 + 16 + 14

= 99 units

Time Complexities
Worst case time complexity of Kruskal’s Algorithm

= O(ElogV) or O(ElogE)

Dijkstra’s Algorithm
Dijkstra's algorithm allows us to find the shortest path between any two
vertices of a graph.
Dijkstra algorithm is a single-source shortest path algorithm.
Here, single-source means that only one source is given, and we have to
find the shortest path from the source to all the nodes.

Dijkstra’s Algorithm Implementation

e
ov
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.

M
ch
Te
PRACTICE PROBLEMS BASED ON DIJKSTRA’S ALGORITHM
It is easier to start with an example and then think about the algorithm.

S tart with a weighted graph

C hoose a starting vertex and assign infinity path values to all other devices

Go to each vertex and update its path length

If the path length of the adjacent vertex is lesser than new path length, don't

update it

Avoid updating path lengths of already visited vertices

e
After each iteration, we pick the unvisited vertex with the least path length.

So we choose 5 before 7

M
ov

c h
Te
Notice how the rightmost vertex has its path length updated twice

Repeat until all the vertices have been visited

Time Complexities
Time Complexity: O(E Log V)

where, E is the number of edges and V is the number of vertices.

Time Complexities
S pace Complexity: O(V)

Dijkstra’s Algorithm Application

To find the shortest path
In social networking applications
In a telephone network
To find the locations in the map

PRACTICE PROBLEMS BASED ON DIJKSTRA’S ALGORITHM

It is easier to start with an example and then think about the algorithm.

9
F E

2 6

14 11
C
D
9

10
A 15
7

o r e
S u c D estination

A B C D E F

0 ∞ ∞ ∞ ∞ ∞

A->B 7 9 ∞ ∞ 14

e
A,B,C 7 9 22 ∞ 14

A,B,C,F 7 9 20 ∞ 11

ov
A,B,C,F,D 7 9 20 20 11

A,B,C,F,D,E 7 9 20 20 11

M
h
A,B,C,F,D,E 7 9 20 20 11

c
F nali solution:

Te
9
F E

11
C
D
9

A
7

A->B, A->C, A->C->F, A->C->D, A->C->F->E

Bellman Ford Algorithm

It is a single-source shortest path algorithm.
algorithm helps us find the shortest path from a vertex to all other vertices
of a weighted graph.
There are various other algorithms used to find the shortest path like
Dijkstra algorithm, etc.
If the weighted graph contains the negative weight values, then the
Dijkstra algorithm does not confirm whether it produces the correct
answer or not.
In contrast to Dijkstra algorithm, bellman ford algorithm guarantees the
correct answer even if the weighted graph contains the negative weight
values.

B A B C
-8
10
0 ∞ ∞

A C AC 10 5

5 ACB 10 5

10
10
B B
10 -8 10 -8

A C A A C
5
5 5
2
Every edge relax time: (V-1)+1

How Bellman Ford's algorithm works

Bellman Ford algorithm works by overestimating the length of the path
from the starting vertex to all other vertices. Then it iteratively relaxes
those estimates by finding new paths that are shorter than the
previously overestimated paths.

e
M
ov

ch
Te

Bellman Ford Algorithm Application

or calculating shortest paths in routing algorithms
F

or finding the shortest path

F

Time Complexities
Best Case ComplexityO(E)

Average Case ComplexityO(VE)

Worst Case ComplexityO(VE)

Space Complexities
S pace Complexity: O(V)

PRACTICE PROBLEMS BASED ON Bellman Ford’s ALGORITHM

e
M
ov

ch
e
To find the shortest path of the above graph, the first step is note down all

T
the edges which are given below:

(A, B), (A, C), (A, D), (B, E), (C, E), (D, C), (D, F), (E, F), (C, B)

The source vertex as 'A'; therefore, the distance value at vertex A is 0 and
the distance value at all the other vertices as infinity.

S ince the graph has six vertices so it will have five iterations.

First iteration

Consider the edge (A, B). Denote vertex 'A' as 'u' and vertex 'B' as 'v'. Now
use the relaxing formula:

d(u) = 0

d(v) = ∞

c(u , v) = 6

Since (0 + 6) is less than ∞, so update

d(v) = d(u) + c(u , v)

d(v) = 0 + 6 = 6

Therefore, the distance of vertex B is 6.

Consider the edge (A, C). Denote vertex 'A' as 'u' and vertex 'C' as 'v'. Now
use the relaxing formula:

d(u) = 0

d(v) = ∞

c(u , v) = 4

Since (0 + 4) is less than ∞, so update

d(v) = d(u) + c(u , v)

d(v) = 0 + 4 = 4

Therefore, the distance of vertex C is 4.

similar we perform for all vertex.......

Second iteration

In the second iteration, we again check all the edges. The first edge is (A, B).
Since (0 + 6) is greater than 1 so there would be no updation in the vertex B.

The next edge is (A, C). Since (0 + 4) is greater than 3 so there would be no
updation in the vertex C.

The next edge is (A, D). Since (0 + 5) equals to 5 so there would be no

updation in the vertex D.

The next edge is (B, E). Since (1 - 1) equals to 0 which is less than 5 so
update:

d(v) = d(u) + c(u, v)

d(E) = d(B) +c(B , E)

= 1 - 1 = 0

The next edge is (C, E). Since (3 + 3) equals to 6 which is greater than 5 so
there would be no updation in the vertex E.

The next edge is (D, C). Since (5 - 2) equals to 3 so there would be no

updation in the vertex C.

The next edge is (D, F). Since (5 - 1) equals to 4 so there would be no

updation in the vertex F.

e
The next edge is (E, F). Since (5 + 3) equals to 8 which is greater than 4 so
there would be no updation in the vertex F.

ov
The next edge is (C, B). Since (3 - 2) equals to 1` so there would be no
updation in the vertex B.

M
ch
Third iteration

Te
We will perform the same steps as we did in the previous iterations. We will
observe that there will be no updation in the distance of vertices.

The following are the distances of vertices:

A: 0

B: 1

C: 3

D: 5

E: 0

F: 3

Drawbacks of Bellman ford algorithm

The bellman ford algorithm does not produce a correct answer if the sum of
the edges of a cycle is negative.

Knapsack Problem
A knapsack (kind of shoulder bag) with limited weight capacity.
Few items each having some weight and value.
The problem states
The value or profit obtained by putting the items into the knapsack is
maximum
And the weight limit of the knapsack does not exceed.

Ex amples:
Item Weight Value

e
ov
1 18 2 5

2 15 24

C apacity 20Kg
3 10 1 5

M
Greedy About value:
Greedy About Weight:

h
25+2/15*24 = 28.2 15+10/15*24 = 31

c
Greedy About Both Weight and Value:

e
Item Weight Value V/W

T
1 18 2 5 1.3

2 15 24 1.6

3 10 1 5 1.5

Sorting: 1.6, 1.5, 1.3

Sol: 24+5/10*15 =31.5

Knapsack Problem Variants

K napsack problem has the following two variants
Fractional Knapsack Proble
0/1 Knapsack Problem

Fractional Knapsack Problem

In Fractional Knapsack Problem
As the name suggests, items are divisible here
We can even put the fraction of any item into the knapsack if taking
the complete item is not possible
It is solved using Greedy Method.

Fractional Knapsack Problem Using Greedy Method

F or each item, compute its value / weight ratio.
Arrange all the items in decreasing order of their value / weight ratio.
Start putting the items into the knapsack beginning from the item with
the highest ratio.

Time Complexity
The main time taking step is the sorting of all items in decreasing order of
their value / weight ratio
If the items are already arranged in the required order, then while loop
takes O(n) time
The average time complexity of Quick Sort is O(nlogn)
Therefore, total time taken including the sort is O(nlogn).

PRACTICE PROBLEM BASED ON FRACTIONAL

KNAPSACK PROBLEM
For the given set of items and knapsack capacity = 60 kg, find the optimal
solution for the fractional knapsack problem making use of greedy approach.

Item Weight Value

1 5 3 0

2 10 40

3 1 5 4 5

4 22 77

5 2 5 90

OR

Find the optimal solution for the fractional knapsack problem making use of
greedy approach. Consider-

n = 5

w = 60 kg

(w1, w2, w3, w4, w5) = (5, 10, 15, 22, 25)

(b1, b2, b3, b4, b5) = (30, 40, 45, 77, 90)

Solution-

S tep-01: Compute the value / weight ratio for each item-

e
S tep-02: Sort all the items in decreasing order of their value / weight ratio-

I1 I2 I5 I4 I3

o
(6) (4) (3.6) (3.5) (3)

S tep-03: Start filling the knapsack by putting the items into it one by one.
v
M
c h
Now
K
Te
napsack weight left to be filled is 20 kg but item-4 has a weight of 22 kg
Since in fractional knapsack problem, even the fraction of any item can be
taken
So, knapsack will contain the following items-

< I1 , I2 , I5 , (20/22) I4 >

Total cost of the knapsack

= 160 + (20/22) x 77

= 160 + 70

= 230 units