Unit 4: Greedy Algorithms

4.1 Greedy Method

 Greedy algorithms are a class of algorithms that make locally
optimal choices at each step with the hope of finding a global
optimum solution.
 In these algorithms, decisions are made based on the information available
at the current moment without considering the consequences of these
decisions in the future. The key idea is to select the best possible choice at
each step, leading to a solution that may not always be the most optimal but
is often good enough for many problems.
 It operates on the principle of “taking the best option now” without
considering the long-term consequences.

Applications of Greedy Algorithm

There are many applications of the greedy method in DAA. Some important
greedy algorithm applications are:
 Assigning tasks to resources to minimize waiting time or maximize efficiency.
 Selecting the most valuable items to fit into a knapsack with limited capacity.
 Dividing an image into regions with similar characteristics.
 Reducing the size of data by removing redundant information.

Disadvantages/Limitations of Using a Greedy Algorithm

Below are some disadvantages of the Greedy Algorithm:

 Greedy algorithms may not always find the best possible solution.
 The order in which the elements are considered can significantly impact the
outcome.
 Greedy algorithms focus on local optimizations and may miss better solutions
that require considering a broader context.
 Greedy algorithms are not applicable to problems where the greedy choice
does not lead to an optimal solution.

4.2 Travelling Salesman Problem

The travelling salesman problem is a graph computational problem where the

salesman needs to visit all cities (represented using nodes in a graph) in a list just
once and the distances (represented using edges in the graph) between all these
cities are known. The solution that is needed to be found for this problem is the
shortest possible route in which the salesman visits all the cities and returns to the
origin city.

If you look at the graph below, considering that the salesman starts from the vertex
‘a’, they need to travel through all the remaining vertices b, c, d, e, f and get back
to ‘a’ while making sure that the cost taken is minimum.

There are various approaches to find the solution to the travelling salesman
problem: naive approach, greedy approach, dynamic programming approach, etc.
In this tutorial we will be learning about solving travelling salesman problem using
greedy approach.
Travelling Salesperson Algorithm
As the definition for greedy approach states, we need to find the best optimal
solution locally to figure out the global optimal solution. 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. The shortest path of graph G starting from one vertex returning to the same
vertex is obtained as the output.

Algorithm
 Travelling salesman problem takes a graph G {V, E} as an input and declare
another graph as the output (say G’) which will record the path the salesman
is going to take from one node to another.
 The algorithm begins by sorting all the edges in the input graph G from the
least distance to the largest distance.
 The first edge selected is the edge with least distance, and one of the two
vertices (say A and B) being the origin node (say A).
 Then among the adjacent edges of the node other than the origin node (B),
find the least cost edge and add it onto the output graph.
 Continue the process with further nodes making sure there are no cycles in
the output graph and the path reaches back to the origin node A.
 However, if the origin is mentioned in the given problem, then the solution
must always start from that node only. Let us look at some example
problems to understand this better.

Examples

Consider the following graph with six cities and the distances between them −
From the given graph, since the origin is already mentioned, the solution must
always start from that node. Among the edges leading from A, A → B has the
shortest distance.

Then, B → C has the shortest and only edge between, therefore it is included in the
output graph.
There’s only one edge between C → D, therefore it is added to the output graph.

There’s two outward edges from D. Even though, D → B has lower distance than
D → E, B is already visited once and it would form a cycle if added to the output
graph. Therefore, D → E is added into the output graph.
There’s only one edge from e, that is E → F. Therefore, it is added into the output
graph.

Again, even though F → C has lower distance than F → A, F → A is added into

the output graph in order to avoid the cycle that would form and C is already
visited once.
The shortest path that originates and ends at A is A → B → C → D → E → F → A

The cost of the path is: 16 + 21 + 12 + 15 + 16 + 34 = 114.

Even though, the cost of path could be decreased if it originates from other nodes
but the question is not raised with respect to that.

4.3 Prim’s Minimal Spanning Tree Algorithm

What is a Spanning Tree?
 A spanning tree is a subset of Graph G, such that all the vertices are
connected using minimum possible number of edges. Hence, a spanning
tree does not have cycles and a graph may have more than one spanning
tree.

What is a minimum spanning tree?

 A minimum spanning tree (MST) is defined as a spanning tree that
has the minimum weight among all the possible spanning trees
The algorithm starts with an empty spanning tree. The idea is to maintain two sets
of vertices. The first set contains the vertices already included in the MST, and
the other set contains the vertices not yet included. At every step, it considers all
the edges that connect the two sets and picks the minimum weight edge from
these edges. After picking the edge, it moves the other endpoint of the edge to the
set containing 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:

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.

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.

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].
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).

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

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

Step 9: Only the vertex 4 remains to be included. The minimum weighted edge
from the incomplete MST to 4 is {3, 4}.
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.
4.4 Kruskals’s Minimal Spanning Tree
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.

Kruskal’s algorithm to find the minimum cost spanning tree uses the greedy
approach. The Greedy Choice is to pick the smallest weight edge that does not
cause a cycle in the MST constructed so far. Let us understand it with an
example:

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

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.
Step 2: Pick edge 8-2. No cycle is formed, include it.
Step 3: Pick edge 6-5. No cycle is formed, include it.

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

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

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

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.
Note: Since the number of edges included in the MST equals to (V – 1), so the
algorithm stops here

4.5 Dijkstra’s Shortest Path Algorithm

The algorithm maintains a set of visited vertices and a set of unvisited vertices. It
starts at the source vertex and iteratively selects the unvisited vertex with the
smallest tentative distance from the source. It then visits the neighbors of this
vertex and updates their tentative distances if a shorter path is found. This process
continues until the destination vertex is reached, or all reachable vertices have
been visited.

Need for Dijkstra’s Algorithm (Purpose and Use-Cases)

The need for Dijkstra’s algorithm arises in many applications where finding the
shortest path between two points is crucial.
For example, It can be used in the routing protocols for computer networks and
also used by map systems to find the shortest path between starting point and the
Destination (as explained in How does Google Maps work?)

Can Dijkstra’s Algorithm work on both Directed and Undirected

graphs?
Yes, Dijkstra’s algorithm can work on both directed graphs and undirected graphs
as this algorithm is designed to work on any type of graph as long as it meets the
requirements of having non-negative edge weights and being connected.
 In a directed graph, each edge has a direction, indicating the direction of
travel between the vertices connected by the edge. In this case, the algorithm
follows the direction of the edges when searching for the shortest path.
 In an undirected graph, the edges have no direction, and the algorithm can
traverse both forward and backward along the edges when searching for the
shortest path.

Algorithm for Dijkstra’s Algorithm:

1. Mark the source node with a current distance of 0 and the rest with infinity.
2. Set the non-visited node with the smallest current distance as the current node.
3. For each neighbor, N of the current node adds the current distance of the
adjacent node with the weight of the edge connecting 0->1. If it is smaller than
the current distance of Node, set it as the new current distance of N.
4. Mark the current node 1 as visited.
5. Go to step 2 if there are any nodes are unvisited.

How does Dijkstra’s Algorithm works?

Let’s see how Dijkstra’s Algorithm works with an example given below:
Dijkstra’s Algorithm will generate the shortest path from Node 0 to all other
Nodes in the graph.

The algorithm will generate the shortest path from node 0 to all the other nodes in
the graph.
For this graph, we will assume that the weight of the edges represents the
distance between two nodes.
As, we can see we have the shortest path from,
Node 0 to Node 1, from
Node 0 to Node 2, from
Node 0 to Node 3, from
Node 0 to Node 4, from
Node 0 to Node 6.
 Initially we have a set of resources given below :
 The Distance from the source node to itself is 0. In this example the source
node is 0.
 The distance from the source node to all other node is unknown so we mark all
of them as infinity.
Example: 0 -> 0, 1-> ∞,2-> ∞,3-> ∞,4-> ∞,5-> ∞,6-> ∞.
 we’ll also have an array of unvisited elements that will keep track of unvisited
or unmarked Nodes.
 Algorithm will complete when all the nodes marked as visited and the distance
between them added to the path. Unvisited Nodes:- 0 1 2 3 4 5 6.

Step 1: Start from Node 0 and mark Node as visited as you can check in below
image visited Node is marked red.
Step 2: Check for adjacent Nodes, Now we have to choices (Either choose Node1
with distance 2 or either choose Node 2 with distance 6 ) and choose Node with
minimum distance. In this step Node 1 is Minimum distance adjacent Node, so
marked it as visited and add up the distance.
Distance: Node 0 -> Node 1 = 2

Step 3: Then Move Forward and check for adjacent Node which is Node 3, so
marked it as visited and add up the distance, Now the distance will be:
Distance: Node 0 -> Node 1 -> Node 3 = 2 + 5 = 7
Step 4: Again we have two choices for adjacent Nodes (Either we can choose
Node 4 with distance 10 or either we can choose Node 5 with distance 15) so
choose Node with minimum distance. In this step Node 4 is Minimum distance
adjacent Node, so marked it as visited and add up the distance.
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 = 2 + 5 + 10 = 17

Step 5: Again, Move Forward and check for adjacent Node which is Node 6, so
marked it as visited and add up the distance, Now the distance will be:
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 -> Node 6 = 2 + 5 + 10 + 2 =
19

So, the Shortest Distance from the Source Vertex is 19 which is optimal one