Module 3:Greedy Method

Approach
CSE IOT_SE_Analysis of Algorithms
Pranita Pingale
Assistant Professor
Dept. of CSE IOT,
SIES Graduate School of Technology

Pranita Pingale 1
Module 3:Greedy Method Approach
3.1 General Method, Single source shortest path: Dijkstra Algorithm
Fractional Knapsack problem, Job sequencing with deadlines, Minimum
cost spanning trees: Kruskal and Prims algorithms

Pranita Pingale 2
Greedy method
• 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. The main function of this
approach is that the decision is taken on the basis of the currently
available information.
• The following are the characteristics of a greedy method:
• To construct the solution in an optimal way, this algorithm creates two
sets where one set contains all the chosen items, and another set
contains the rejected items.
• A Greedy algorithm makes good local choices in the hope that the
solution should be either feasible or optimal.
Pranita Pingale 3
➢Applications of Greedy Algorithm:

• It is used in finding the shortest path.

• It is used to find the minimum spanning tree using the prim's
algorithm or the Kruskal's algorithm.
• It is used in a job sequencing with a deadline.
• This algorithm is also used to solve the fractional knapsack problem.

Pranita Pingale 4
Introduction to Graphs
• Graphs are non-linear data structures representing the "connections" between the
elements.
• These elements are known as the Vertices, and the lines or arcs that connect any two
vertices in the graph are known as the Edges.
• More formally, a Graph comprises a set of Vertices (V) and a set of Edges (E). The
Graph is denoted by G(V, E).

Pranita Pingale 5
Types of Graphs
• Undirected Graph: A Graph with edges that do not have a direction is
termed an Undirected Graph. The edges of this graph imply a two-
way relationship in which each edge can be traversed in both
directions.

Pranita Pingale 6
• Directed Graph: A Graph with edges with direction is termed a Directed Graph.
The edges of this graph imply a one-way relationship in which each edge can only
be traversed in a single direction.

• Weighted Graphs: A Graph is said to be Weighted if each edge is assigned a

'weight'. The weight of an edge can denote distance, time, or anything that
models the 'connection' between the pair of vertices it connects.

Pranita Pingale 7
Single source shortest path: Dijkstra Algorithm
➢How does Google Maps finds the shortest and fastest route between
two places?
• Dijkstra's Algorithm is a Graph algorithm that finds the shortest
path from a source vertex to all other vertices in the Graph (single
source shortest path).
• It is a type of Greedy Algorithm that only works on Weighted Graphs
having positive weights.
• The time complexity of Dijkstra's Algorithm is O(V2) with the help of
the adjacency matrix representation of the graph.
• This time complexity can be reduced to O((V + E) log V) with the help
of an adjacency list representation of the graph, where V is the
number of vertices and E is the number of edges in the graph.

Pranita Pingale 8
Pranita Pingale 9
Working of Dijkstra's Algorithm
• A graph and source vertex are requirements for Dijkstra's Algorithm.
This Algorithm is established on Greedy Approach and thus finds the
locally optimal choice (local minima in this case) at each step of the
Algorithm.

➢Each Vertex in this Algorithm will have two properties defined for it:
• Visited Property
• Path Property

Pranita Pingale 10
Pranita Pingale 11
Algorithm
function Dijkstra_Algorithm(Graph, source_node)
// iterating through the nodes in Graph and set their distances to INFINITY
for each node N in Graph:
distance[N] = INFINITY
previous[N] = NULL
If N != source_node, add N to Priority Queue G
// setting the distance of the source node of the Graph to 0
distance[source_node] = 0

// iterating until the Priority Queue G is not empty

while G is NOT empty:
// selecting a node Q having the least distance and marking it as visited
Q = node in G with the least distance[]
mark Q visited

Pranita Pingale 12
// iterating through the unvisited neighbouring nodes of the node Q and performin
g relaxation accordingly
for each unvisited neighbour node N of Q:
temporary_distance = distance[Q] + distance_between(Q, N)

// if the temporary distance is less than the given distance of the path to the
Node, updating the resultant distance with the minimum value
if temporary_distance < distance[N]
distance[N] := temporary_distance
previous[N] := Q

// returning the final list of distance

return distance[], previous[]

Pranita Pingale 13
Example

Pranita Pingale 14
Pranita Pingale 15
➢Advantages of Dijkstra's Algorithm:
• One primary advantage of using Dijkstra's Algorithm is that it has an
almost linear time and space complexity.
• We can use this algorithm to calculate the shortest path from a single
vertex to all other vertices and a single source vertex to a single
destination vertex by stopping the algorithm once we get the shortest
distance for the destination vertex.
• This algorithm only works for directed weighted graphs, and all the
edges of this graph should be non-negative.

Pranita Pingale 16
➢Disadvantages Dijkstra's algorithm:
• Dijkstra's Algorithm performs a concealed exploration that utilizes a lot of time
during the process.
• This algorithm is impotent to handle negative edges.
• Since this algorithm heads to the acyclic graph, it cannot calculate the exact
shortest path.
• It also requires maintenance to keep a record of vertices that have been visited.

➢Applications:
• Digital Mapping Services in Google Maps
• Social Networking Applications
• Telephone Network
• Flight Program
• IP routing to find Open Shortest Path First
• Robotic Path

Pranita Pingale 17
➢Knapsack Problem-
• A knapsack (kind of shoulder bag) with limited weight capacity.
• Few items each having some weight and value(profit).

❑Placed item into the knapsack such that-

• The value or profit obtained by putting the items into the knapsack is
maximum and the weight limit of the knapsack does not exceed.

❑Knapsack problem has the following two variants-

• Fractional Knapsack Problem
• 0/1 Knapsack Problem

Pranita Pingale 18
Fractional Knapsack problem

Pranita Pingale 19
Steps to solve fractional knapsack problem:
• Step-01:
For each item, compute its value / weight ratio.
• Step-02:
Arrange all the items in decreasing order of their value / weight ratio.
• Step-03:
Start putting the items into the knapsack beginning from the item with
the highest ratio.
Put as many items as you can into the knapsack.

Pranita Pingale 20
Job sequencing with deadlines

Pranita Pingale 21
Pranita Pingale 22
Step-01:
• Sort all the given jobs in decreasing order of their profit.
Step-02:
• Check the value of maximum deadline.
• Draw a Gantt chart where maximum time on Gantt chart is the value
of maximum deadline.
Step-03:
• Pick up the jobs one by one.
• Put the job on Gantt chart as far as possible from 0 ensuring that the
job gets completed before its deadline.

Pranita Pingale 23
Pranita Pingale 24
Pranita Pingale 25
Pranita Pingale 26
Pranita Pingale 27
Pranita Pingale 28
Pranita Pingale 29
• The optimal schedule is-
J2 , J4 , J3 , J5 , J1
• This is the required order in which the jobs must be completed in order to
obtain the maximum profit.
• All the jobs are not completed in optimal schedule.
• This is because job J6 could not be completed within its deadline.
• Maximum earned profit= Sum of profit of all the jobs in optimal schedule
= Profit of job J2 + Profit of job J4 + Profit of job J3 + Profit of job J5 + Profit of
job J1
= 180 + 300 + 190 + 120 + 200
= 990 units

Pranita Pingale 30
Solve using Job sequencing with deadlines

Jobs (N=5) J1 J2 J3 J4 J5

Profit 20 15 10 5 1

Deadlines 2 2 1 3 3

Pranita Pingale 31
Minimum cost spanning trees: Kruskal’s and Prim’s algorithms
Spanning Tree:

• A spanning tree can be defined as the sub graph of an undirected connected

graph.
• It includes all the vertices along with the least possible number of edges.
• If any vertex is missed, it is not a spanning tree.
• A spanning tree is a subset of the graph that does not have cycles, and it also
cannot be disconnected.

Pranita Pingale 32
• The above graph can be represented as G(V, E), where 'V' is the number of
vertices, and 'E' is the number of edges. The spanning tree of the above graph
would be represented as G`(V`, E`).
• In this case, V` = V means that the number of vertices in the spanning tree
would be the same as the number of vertices in the graph, but the number of
edges would be different.
• The number of edges in the spanning tree is the subset of the number of
edges in the original graph. Therefore, the number of edges can be written as:

• E` € E
• It can also be written as:
• E` = |V| - 1

Pranita Pingale 33
• Two conditions exist in the spanning tree, which is as follows:
• The number of vertices in the spanning tree would be the same as the number
of vertices in the original graph.
V` = V

• The number of edges in the spanning tree would be equal to the number of
edges minus 1.
E` = |V| - 1

• The spanning tree should not contain any cycle.

• The spanning tree should not be disconnected.

Pranita Pingale 34
• The above graph contains 5 vertices. As we know, the vertices in the
spanning tree would be the same as the graph; therefore, V` is equal
5. The number of edges in the spanning tree would be equal to (5 - 1),
i.e., 4. The following are the possible spanning trees:

Pranita Pingale 35
Pranita Pingale 36
Pranita Pingale 37
Pranita Pingale 38
Pranita Pingale 39
❖Methods of Minimum Spanning Tree
• There are two methods to find Minimum Spanning Tree
1. Kruskal's Algorithm
2. Prim's Algorithm

• Kruskal's Algorithm:
• Kruskal’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

Pranita Pingale 40
Kruskal's Algorithm steps:

Pranita Pingale 41
Pranita Pingale 42
Pranita Pingale 43
Pranita Pingale 44
Pranita Pingale 45
Pranita Pingale 46
• Since all the vertices have been connected / included in the MST, so
we stop.
• Weight of the MST
= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
=99 units

Pranita Pingale 47
Pranita Pingale 48
• e → f, h→ i ,b → h, d → f [cycle will be formed]

Pranita Pingale 49
 Kruskal’s Algorithm Time Complexity-
• The edges are maintained as min heap.
• The next edge can be obtained in O(logE) time if graph has E edges.
• Reconstruction of heap takes O(E) time.
• So, Kruskal’s Algorithm takes O(ElogE) time.
• The value of E can be at most O(V2).
• So, O(logV) and O(logE) are same.
• If the edges are already sorted, then there is no need to construct min
heap.
• So, deletion from min heap time is saved.
• In this case, time complexity of Kruskal’s Algorithm = O(E + V)
Pranita Pingale 50
• Prim's Algorithm:
• Prim’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.

Pranita Pingale 51
• 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.
• We traverse all the vertices of graph using breadth first search and use a min heap for
storing the vertices not yet included in the MST.
• To get the minimum weight edge, we use min heap as a priority queue.
• 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)

• This time complexity can be improved and reduced to O(E + VlogV) using Fibonacci
heap.

Pranita Pingale 52
Pranita Pingale 53
Pranita Pingale 54
Pranita Pingale 55
Pranita Pingale 56
• Since all the vertices have been included in the MST, so we stop.
• Now, Cost of Minimum Spanning Tree
= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units

Pranita Pingale 57
Thank You!
(pranitasp@[Link])

Pranita Pingale 58