Unit V

Greedy Technique

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. Let's understand through some terms.

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. Whatever the current information is present, the decision is
made without worrying about the effect of the current decision in future.

This technique is basically used to determine the feasible solution that may or may not be
optimal. The feasible solution is a subset that satisfies the given criteria. The optimal solution is
the solution which is the best and the most favorable solution in the subset. In the case of
feasible, if more than one solution satisfies the given criteria then those solutions will be
considered as the feasible, whereas the optimal solution is the best solution among all the
solutions.

Characteristics of Greedy method

o 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.
o A Greedy algorithm makes good local choices in the hope that the solution should be
either feasible or optimal.

Applications of Greedy Algorithm

o It is used in finding the shortest path.

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

Pseudo code of Greedy Algorithm

1. Algorithm Greedy (a, n)

2. {
3. Solution : = 0;
4. for i = 0 to n do
5. {
6. x: = select(a);
7. if feasible(solution, x)
8. {
9. Solution: = union(solution , x)
10. }
11. return solution;
12. } }

The above is the greedy algorithm. Initially, the solution is assigned with zero value. We pass the
array and number of elements in the greedy algorithm. Inside the for loop, we select the
element one by one and checks whether the solution is feasible or not. If the solution is feasible,
then we perform the union.

Let's understand through an example.

Suppose there is a problem 'P'. I want to travel from A to B shown as below:

P:A→B

The problem is that we have to travel this journey from A to B. There are various solutions to go
from A to B. We can go from A to B by walk, car, bike, train, aeroplane, etc. There is a
constraint in the journey that we have to travel this journey within 12 hrs. If I go by train or
aeroplane then only, I can cover this distance within 12 hrs. There are many solutions to this
problem but there are only two solutions that satisfy the constraint.

If we say that we have to cover the journey at the minimum cost. This means that we have to
travel this distance as minimum as possible, so this problem is known as a minimization
problem. Till now, we have two feasible solutions, i.e., one by train and another one by air. Since
travelling by train will lead to the minimum cost so it is an optimal solution. An optimal solution
is also the feasible solution, but providing the best result so that solution is the optimal solution
with the minimum cost. There would be only one optimal solution.

The problem that requires either minimum or maximum result then that problem is known as an
optimization problem. Greedy method is one of the strategies used for solving the optimization
problems.

If we say that we have to cover the journey at the minimum cost. This means that we have to
travel this distance as minimum as possible, so this problem is known as a minimization
problem. Till now, we have two feasible solutions, i.e., one by train and another one by air. Since
travelling by train will lead to the minimum cost so it is an optimal solution. An optimal solution
is also the feasible solution, but providing the best result so that solution is the optimal solution
with the minimum cost. There would be only one optimal solution.

The problem that requires either minimum or maximum result then that problem is known as an
optimization problem. Greedy method is one of the strategies used for solving the optimization
problems.

A spanning tree consists of (n-1) edges, where 'n' is the number of vertices (or nodes). Edges of
the spanning tree may or may not have weights assigned to them. All the possible spanning
trees created from the given graph G would have the same number of vertices, but the number
of edges in the spanning tree would be equal to the number of vertices in the given graph
minus 1.

A complete undirected graph can have nn-2 number of spanning trees where n is the number of
vertices in the graph. Suppose, if n = 5, the number of maximum possible spanning trees would
be 55-2 = 125.

Applications of the spanning tree

Basically, a spanning tree is used to find a minimum path to connect all nodes of the graph.
Some of the common applications of the spanning tree are listed as follows -

o Cluster Analysis
o Civil network planning
o Computer network routing protocol

Now, let's understand the spanning tree with the help of an example.

Example of Spanning tree

Suppose the graph be -
As discussed above, a spanning tree contains the same number of vertices as the graph, the
number of vertices in the above graph is 5; therefore, the spanning tree will contain 5 vertices.
The edges in the spanning tree will be equal to the number of vertices in the graph minus 1. So,
there will be 4 edges in the spanning tree.

ADVERTISEMENT

Some of the possible spanning trees that will be created from the above graph are given as
follows -
Properties of spanning-tree
Some of the properties of the spanning tree are given as follows -

o There can be more than one spanning tree of a connected graph G.

o A spanning tree does not have any cycles or loop.
o A spanning tree is minimally connected, so removing one edge from the tree will make
the graph disconnected.
o A spanning tree is maximally acyclic, so adding one edge to the tree will create a loop.
o There can be a maximum nn-2 number of spanning trees that can be created from a
complete graph.
o A spanning tree has n-1 edges, where 'n' is the number of nodes.
o If the graph is a complete graph, then the spanning tree can be constructed by removing
maximum (e-n+1) edges, where 'e' is the number of edges and 'n' is the number of
vertices.

So, a spanning tree is a subset of connected graph G, and there is no spanning tree of a
disconnected graph.

Minimum Spanning tree

A minimum spanning tree can be defined as the spanning tree in which the sum of the weights
of the edge is minimum. The weight of the spanning tree is the sum of the weights given to the
edges of the spanning tree. In the real world, this weight can be considered as the distance,
traffic load, congestion, or any random value.
Example of minimum spanning tree
Let's understand the minimum spanning tree with the help of an example.

The sum of the edges of the above graph is 16. Now, some of the possible spanning trees
created from the above graph are -

So, the minimum spanning tree that is selected from the above spanning trees for the given weighted graph is
-
Applications of minimum spanning tree

The applications of the minimum spanning tree are given as follows -

o Minimum spanning tree can be used to design water-supply networks,

telecommunication networks, and electrical grids.
o It can be used to find paths in the map.

Algorithms for Minimum spanning tree

A minimum spanning tree can be found from a weighted graph by using the algorithms given
below -

o Prim's Algorithm
o Kruskal's Algorithm

Prim's algorithm - It is a greedy algorithm that starts with an empty spanning tree. It is used to
find the minimum spanning tree from the graph. This algorithm finds the subset of edges that
includes every vertex of the graph such that the sum of the weights of the edges can be
minimized.

Kruskal's algorithm - This algorithm is also used to find the minimum spanning tree for a
connected weighted graph. Kruskal's algorithm also follows greedy approach, which finds an
optimum solution at every stage instead of focusing on a global optimum.

Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning tree from a
graph. Prim's algorithm finds the subset of edges that includes every vertex of the graph such
that the sum of the weights of the edges can be minimized.

Prim's algorithm starts with the single node and explores all the adjacent nodes with all the
connecting edges at every step. The edges with the minimal weights causing no cycles in the
graph got selected.

How does the prim's algorithm work?

Prim's algorithm is a greedy algorithm that starts from one vertex and continue to add the
edges with the smallest weight until the goal is reached. The steps to implement the prim's
algorithm are given as follows -

o First, we have to initialize an MST with the randomly chosen vertex.

 o Now, we have to find all the edges that connect the tree in the above step with the new
vertices. From the edges found, select the minimum edge and add it to the tree.
o Repeat step 2 until the minimum spanning tree is formed.

The applications of prim's algorithm are -

o Prim's algorithm can be used in network designing.

o It can be used to make network cycles.
o It can also be used to lay down electrical wiring cables.

Example of prim's algorithm

Now, let's see the working of prim's algorithm using an example. It will be easier to understand
the prim's algorithm using an example.

Suppose, a weighted graph is -

Step 1 - First, we have to choose a vertex from the above graph. Let's choose B.
Step 2 - Now, we have to choose and add the shortest edge from vertex B. There are two edges
from vertex B that are B to C with weight 10 and edge B to D with weight 4. Among the edges,
the edge BD has the minimum weight. So, add it to the MST.

Step 3 - Now, again, choose the edge with the minimum weight among all the other edges. In
this case, the edges DE and CD are such edges. Add them to MST and explore the adjacent of C,
i.e., E and A. So, select the edge DE and add it to the MST.

Step 4 - Now, select the edge CD, and add it to the MST.
 Step 5 - Now, choose the edge CA. Here, we cannot select the edge CE as it would create a
cycle to the graph. So, choose the edge CA and add it to the MST.

So, the graph produced in step 5 is the minimum spanning tree of the given graph. The cost of
the MST is given below -

Cost of MST = 4 + 2 + 1 + 3 = 10 units.

Algorithm
1. Step 1: Select a starting vertex
2. Step 2: Repeat Steps 3 and 4 until there are fringe vertices
3. Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight

4. Step 4: Add the selected edge and the vertex to the minimum spanning tree T
5. [END OF LOOP]
6. Step 5: EXIT

Complexity of Prim's algorithm

Now, let's see the time complexity of Prim's algorithm. The running time of the prim's algorithm
depends upon using the data structure for the graph and the ordering of edges. Below table
shows some choices -

o Time Complexity

Data structure used for the minimum edge weight Time Complexity

Adjacency matrix, linear searching O(|V|2)

Adjacency list and binary heap O(|E| log |V|)

Adjacency list and Fibonacci heap O(|E|+ |V| log |V|)

Prim's algorithm can be simply implemented by using the adjacency matrix or adjacency list
graph representation, and to add the edge with the minimum weight requires the linearly
searching of an array of weights. It requires O(|V|2) running time. It can be improved further by
using the implementation of heap to find the minimum weight edges in the inner loop of the
algorithm.

Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted
graph. The main target of the algorithm is to find the subset of edges by using which we can
traverse every vertex of the graph. It follows the greedy approach that finds an optimum
solution at every stage instead of focusing on a global optimum.

How does Kruskal's algorithm work?

In Kruskal's algorithm, we start from edges with the lowest weight and keep adding the edges
until the goal is reached. The steps to implement Kruskal's algorithm are listed as follows -

o First, sort all the edges from low weight to high.

o Now, take the edge with the lowest weight and add it to the spanning tree. If the edge to
be added creates a cycle, then reject the edge.
 o Continue to add the edges until we reach all vertices, and a minimum spanning tree is
created.

The applications of Kruskal's algorithm are -

o Kruskal's algorithm can be used to layout electrical wiring among cities.

o It can be used to lay down LAN connections.

Example of Kruskal's algorithm

Now, let's see the working of Kruskal's algorithm using an example. It will be easier to
understand Kruskal's algorithm using an example.

Suppose a weighted graph is –

The weight of the edges of the above graph is given in the below table -

Edge AB AC AD AE BC CD DE

Weight 1 7 10 5 3 4 2

Now, sort the edges given above in the ascending order of their weights.
Edge AB DE BC CD AE AC AD

Weight 1 2 3 4 5 7 10

Now, let's start constructing the minimum spanning tree.

Step 1 - First, add the edge AB with weight 1 to the MST.

Step 2 - Add the edge DE with weight 2 to the MST as it is not creating the cycle.
Step 3 - Add the edge BC with weight 3 to the MST, as it is not creating any cycle or loop.

Step 4 - Now, pick the edge CD with weight 4 to the MST, as it is not forming the cycle.

Step 5 - After that, pick the edge AE with weight 5. Including this edge will create the cycle, so
discard it.

Step 6 - Pick the edge AC with weight 7. Including this edge will create the cycle, so discard it.

Step 7 - Pick the edge AD with weight 10. Including this edge will also create the cycle, so
discard it.

So, the final minimum spanning tree obtained from the given weighted graph by using Kruskal's
algorithm is -
The cost of the MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

An Introduction to Dijkstra's Algorithm

Now that we know some basic Graphs concepts let's dive into understanding the concept of
Dijkstra's Algorithm.

Ever wondered how does Google Maps finds the shortest and fastest route between two places?

Well, the answer is Dijkstra's Algorithm. 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.

Fundamentals of Dijkstra's Algorithm

The following are the basic concepts of Dijkstra's Algorithm:

1. Dijkstra's Algorithm begins at the node we select (the source node), and it examines the
graph to find the shortest path between that node and all the other nodes in the graph.
2. The Algorithm keeps records of the presently acknowledged shortest distance from each
node to the source node, and it updates these values if it finds any shorter path.
3. Once the Algorithm has retrieved the shortest path between the source and another
node, that node is marked as 'visited' and included in the path.
 4. The procedure continues until all the nodes in the graph have been included in the path.
In this manner, we have a path connecting the source node to all other nodes, following
the shortest possible path to reach each node.

Understanding the 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:

1. Visited Property
2. Path Property

Let us understand these properties in brief.

Visited Property:

1. The 'visited' property signifies whether or not the node has been visited.
2. We are using this property so that we do not revisit any node.
3. A node is marked visited only when the shortest path has been found.

Path Property:

1. The 'path' property stores the value of the current minimum path to the node.
2. The current minimum path implies the shortest way we have reached this node till now.
3. This property is revised when any neighbor of the node is visited.
4. This property is significant because it will store the final answer for each node.

Initially, we mark all the vertices, or nodes, unvisited as they have yet to be visited. The path to
all the nodes is also set to infinity apart from the source node. Moreover, the path to the source
node is set to zero (0).

We then select the source node and mark it as visited. After that, we access all the neighboring
nodes of the source node and perform relaxation on every node. Relaxation is the process of
lowering the cost of reaching a node with the help of another node.
In the process of relaxation, the path of each node is revised to the minimum value amongst the
node's current path, the sum of the path to the previous node, and the path from the previous
node to the current node.

Let us suppose that p[n] is the value of the current path for node n, p[m] is the value of the path
up to the previously visited node m, and w is the weight of the edge between the current node
and previously visited one (edge weight between n and m).

In the mathematical sense, relaxation can be exemplified as:

p[n] = minimum(p[n], p[m] + w)

We then mark an unvisited node with the least path as visited in every subsequent step and
update its neighbor's paths.

We repeat this procedure until all the nodes in the graph are marked visited.

Whenever we add a node to the visited set, the path to all its neighboring nodes also changes
accordingly.

If any node is left unreachable (disconnected component), its path remains 'infinity'. In case the
source itself is a separate component, then the path to all other nodes remains 'infinity'.

Understanding Dijkstra's Algorithm with an Example

The following is the step that we will follow to implement Dijkstra's Algorithm:

Step 1: First, we will mark the source node with a current distance of 0 and set the rest of the
nodes to INFINITY.

Step 2: We will then set the unvisited node with the smallest current distance as the current
node, suppose X.

Step 3: For each neighbor N of the current node X: We will then add the current distance of X
with the weight of the edge joining X-N. If it is smaller than the current distance of N, set it as
the new current distance of N.

Step 4: We will then mark the current node X as visited.

Step 5: We will repeat the process from 'Step 2' if there is any node unvisited left in the graph.

Let us now understand the implementation of the algorithm with the help of an example:
Figure 6: The Given Graph

1. We will use the above graph as the input, with node A as the source.
2. First, we will mark all the nodes as unvisited.
3. We will set the path to 0 at node A and INFINITY for all the other nodes.
4. We will now mark source node A as visited and access its neighboring nodes.
Note: We have only accessed the neighboring nodes, not visited them.
5. We will now update the path to node B by 4 with the help of relaxation because the path
to node A is 0 and the path from node A to B is 4, and the minimum((0 + 4),
INFINITY) is 4.
6. We will also update the path to node C by 5 with the help of relaxation because the path
to node A is 0 and the path from node A to C is 5, and the minimum((0 + 5),
INFINITY) is 5. Both the neighbors of node A are now relaxed; therefore, we can move
ahead.
7. We will now select the next unvisited node with the least path and visit it. Hence, we will
visit node B and perform relaxation on its unvisited neighbors. After performing
relaxation, the path to node C will remain 5, whereas the path to node E will become 11,
and the path to node D will become 13.
 8. We will now visit node E and perform relaxation on its neighboring nodes B, D, and F.
Since only node F is unvisited, it will be relaxed. Thus, the path to node B will remain as it
is, i.e., 4, the path to node D will also remain 13, and the path to node F will become 14
(8 + 6).
9. Now we will visit node D, and only node F will be relaxed. However, the path to
node F will remain unchanged, i.e., 14.
10. Since only node F is remaining, we will visit it but not perform any relaxation as all its
neighboring nodes are already visited.
11. Once all the nodes of the graphs are visited, the program will end.

Hence, the final paths we concluded are:

1. A = 0
2. B = 4 (A -> B)
3. C = 5 (A -> C)
4. D = 4 + 9 = 13 (A -> B -> D)
5. E = 5 + 3 = 8 (A -> C -> E)
6. F = 5 + 3 + 6 = 14 (A -> C -> E -> F)

Pseudocode for Dijkstra's Algorithm

We will now understand a pseudocode for Dijkstra's Algorithm.

o We have to maintain a record of the path distance of every node. Therefore, we can store
the path distance of each node in an array of size n, where n is the total number of
nodes.
o Moreover, we want to retrieve the shortest path along with the length of that path. To
overcome this problem, we will map each node to the node that last updated its path
length.
o Once the algorithm is complete, we can backtrack the destination node to the source
node to retrieve the path.
o We can use a minimum Priority Queue to retrieve the node with the least path distance
in an efficient way.

Let us now implement a pseudocode of the above illustration:

Pseudocode:
1. function Dijkstra_Algorithm(Graph, source_node)
2. // iterating through the nodes in Graph and set their distances to INFINITY
3. for each node N in Graph:
4. distance[N] = INFINITY
5. previous[N] = NULL
6. If N != source_node, add N to Priority Queue G
7. // setting the distance of the source node of the Graph to 0
8. distance[source_node] = 0
9.
10. // iterating until the Priority Queue G is not empty
11. while G is NOT empty:
12. // selecting a node Q having the least distance and marking it as visited
13. Q = node in G with the least distance[]
14. mark Q visited
15.
16. // iterating through the unvisited neighboring nodes of the node Q and performing relaxati
on accordingly
17. for each unvisited neighbor node N of Q:
18. temporary_distance = distance[Q] + distance_between(Q, N)
19.
20. // if the temporary distance is less than the given distance of the path to the Node, upda
ting the resultant distance with the minimum value
21. if temporary_distance < distance[N]
22. distance[N] := temporary_distance
23. previous[N] := Q
24.
25. // returning the final list of distance
26. return distance[], previous[]

Explanation:

In the above pseudocode, we have defined a function that accepts multiple parameters - the
Graph consisting of the nodes and the source node. Inside this function, we have iterated
through each node in the Graph, set their initial distance to INFINITY, and set the previous node
value to NULL. We have also checked whether any selected node is not a source node and
added the same into the Priority Queue. Moreover, we have set the distance of the source node
to 0. We then iterated through the nodes in the priority queue, selected the node with the least
distance, and marked it as visited. We then iterated through the unvisited neighboring nodes of
the selected node and performed relaxation accordingly. At last, we have compared both the
distances (original and temporary distance) between the source node and the destination node,
updated the resultant distance with the minimum value and previous node information, and
returned the final list of distances with their previous node information.