Chapter Three

Greedy Algorithms
 Greedy Algorithm
• An algorithm is designed to achieve optimal solution for
a given problem.
• In greedy approach, decisions are made from the given
solution domain. The closest solution that seems to
provide optimal solution is chosen.
• It tries to find localized optimal solution which may
eventually land in globally optimized solutions.
• Counting Coins : This problem is to count to a desired
value by choosing the least possible coins and the greedy
approach forces the algorithm to pick the largest possible
coin. If we are provided coins of € 1, 2, 5 and 10 and we
are asked to count € 18 then the greedy procedure will be;
Complied by Abebe Z. 2
• 1 - Select one € 10 coin, the remaining count is 8
• 2 - Then select one € 5 coin, the remaining count is 3
• 3 - Then select one € 2 coin, the remaining count is 1
• 3 - And finally, the selection of one € 1 coins solves the
problem
• Though, it seems to be working fine, for this count we need
to pick only 4 coins. But if we slightly change the problem
then the same approach may not be able to produce the
same optimum result.
• Hence, we may conclude that the greedy approach picks an
immediate optimized solution and may fail where global
optimization is a major concern

Complied by Abebe Z. 3
Graph Minimum Spanning Tree
(MST)
• A tree is acyclic, undirected and connected graph.
• A spanning tree of a graph is a tree containing all vertices
from the graph.
• A minimum spanning tree is a spanning tree where the sum
of the weights on the tree’s edges are minimal.
• Find a minimum-cost set of edges that connect all vertices of
a graph.
• Applications:-
• Connect a nodes with minimum of wire
• Networking
• Circuit design
Minimum Spanning tree
 Cont…
• Problem formulation
• Given an undirected weighted graph G=(V,E) with
weights w(u,v) for each edge (u,v) C E.
• Find acyclic subset T C E that connects all of the
vertices V, and minimizes the total weight.

• The minimum spanning tree is (V, T)

• Minimum spanning tree may not unique (can be more than
one).
 Properties of MST
• Important properties:
• A valid MST cannot contain a cycle
• If we add or remove an edge from an MST, it’s no
longer a
valid MST for that graph.
• Adding an edge introduces a cycle; removing an edge
means
vertices are no longer connected.
• If there are |V | vertices, the MST contains exactly | V
| - 1 edges.
• An MST is always a tree.
• If every edge has a unique weight, there exists a
unique MST
Two Algorithms
• Prim: (build tree incrementally)
• Pick lower cost edge connected to known (incomplete)
spanning tree that does not create a cycle and expand to
include it in the tree
• Kruskal: (build forest that will finish as a tree)
• Pick lowest cost edge not yet in a tree that does not
create a cycle. Then expand the set of included edges to
include it. (It will be somewhere in the forest.)

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 9

Prim’s algorithm
1
Starting from empty T,
10 5
choose a vertex at random
and initialize 1
V = {1), E’ ={}
8 3
2 3 4

1 1 6

4
2
6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 10

Prim’s algorithm
1
Choose the vertex u not in V
10 5
such that edge weight from u to
a vertex in V is minimal (greedy!) 1
V={1,3} E’= {(1,3) }
8 3
2 3 4

1 1 6

4
2
6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 11

 Prim’s algorithm
Repeat until all vertices have been
1
chosen
10 5
Choose the vertex u not in V such that
edge weight from v to a vertex in V is 1
minimal (greedy!)
V= {1,3,4} E’= {(1,3),(3,4)} 8 3
2 3 4
V={1,3,4,5} E’={(1,3),(3,4),(4,5)}
…. 6
1 1
V={1,3,4,5,2,6}
E’={(1,3),(3,4),(4,5),(5,2),(2,6)} 4
2
6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 12

 Prim’s algorithm
Repeat until all vertices have been
1
chosen
10 5
V={1,3,4,5,2,6}
1
E’={(1,3),(3,4),(4,5),(5,2),(2,6)}

8 3
Final Cost: 1 + 3 + 4 + 1 + 1 = 10 2 3 4

1 1 6

4
2
6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 13

Prim’s Algorithm Implementation
• Assume adjacency list representation
Initialize connection cost of each node to “inf” and “unmark” them
Choose one node, say v and set cost[v] = 0 and prev[v] =0
While they are unmarked nodes
Select the unmarked node u with minimum cost; mark it
For each unmarked node w adjacent to u
if cost(u,w) < cost(w) then cost(w) := cost (u,w)
prev[w] = u

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 14

Prim’s algorithm Analysis
• If the “Select the unmarked node u with minimum cost” is done
with binary heap then O((n+m)logn)

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 15

Kruskal’s Algorithm
• Select edges in order of increasing cost
• Accept an edge to expand tree or forest only if it
does not cause a cycle
• Implementation using adjacency list, priority
queues and disjoint sets

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 16

Kruskal’s Algorithm
Initialize a forest of trees, each tree being a single node
Build a priority queue of edges with priority being lowest cost
Repeat until |V| -1 edges have been accepted {
Deletemin edge from priority queue
If it forms a cycle then discard it
else accept the edge – It will join 2 existing trees yielding a larger tree
and reducing the forest by one tree
}
The accepted edges form the minimum spanning tree

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 17

Detecting Cycles
• If the edge to be added (u,v) is such that vertices u
and v belong to the same tree, then by adding (u,v)
you would form a cycle
• Therefore to check, Find(u) and Find(v). If they are the
same discard (u,v)
• If they are different Union(Find(u),Find(v))

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 18

Properties of trees in K’s
algorithm
• Vertices in different trees are disjoint
• True at initialization and Union won’t modify the fact for
remaining trees
• Trees form equivalent classes under the relation “is
connected to”
• u connected to u (reflexivity)
• u connected to v implies v connected to u (symmetry)
• u connected to v and v connected to w implies a path
from u to w so u connected to w (transitivity)

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 19

K’s Algorithm Data Structures
• Adjacency list for the graph
• To perform the initialization of the data structures below
• Disjoint Set ADT’s for the trees (recall Up tree
implementation of Union-Find)
• Binary heap for edges

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 20

Example

1
10 5
1 1

8 3
2 3 4

1 1 6

4
2
6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 21

 1
10 5
1 1

8 3
2 3 4

1 1 6

4
2
6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 22

 Initialization
1
Initially, Forest of 6 trees
F= {{1},{2},{3},{4},{5},{6}}

Edges in a heap (not shown)

2 3 4

6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 23

 Step 1
1
Select edge with lowest cost
(2,5)
Find(2) = 2, Find (5) = 5
Union(2,5)
F= {{1},{2,5},{3},{4},{6}} 2 3 4
1 edge accepted
1

6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 24

 Step 2
1
Select edge with lowest cost
(2,6)
Find(2) = 2, Find (6) = 6
Union(2,6)
F= {{1},{2,5,6},{3},{4}} 2 3 4
2 edges accepted
1
1

6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 25

 Step 3
1
Select edge with lowest cost
(1,3)
Find(1) = 1, Find (3) = 3 1
Union(1,3)
F= {{1,3},{2,5,6},{4}} 2 3 4
3 edges accepted
1
1

6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 26

 Step 4
1
Select edge with lowest cost
(5,6)
Find(5) = 2, Find (6) = 2 1
Do nothing
F= {{1,3},{2,5,6},{4}} 2 3 4
3 edges accepted
1
1

6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 27

 Step 5
1
Select edge with lowest cost
(3,4)
Find(3) = 1, Find (4) = 4 1
Union(1,4) 3
2 3 4
F= {{1,3,4},{2,5,6}}
4 edges accepted
1
1

6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 28

 Step 6
Select edge with lowest cost
1
(4,5)
Find(4) = 1, Find (5) = 2
Union(1,2) 1
F= {{1,3,4,2,5,6}} 3
2 3 4
5 edges accepted : end
Total cost = 10
Although there is a unique 1
4
spanning tree in this example, 1
this is not generally the case
6 5

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 29

Kruskal’s Algorithm Analysis
• Initialize forest O(n)
• Initialize heap O(m), m = |E|
• Loop performed m times
• In the loop one DeleteMin O(log m)
• Two Find, each O(log n)
• One Union (at most) O(1)
• So worst case O(m log m) = O(m log n)

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 30

Time Complexity Summary
• Recall that m = |E| = O(V2) = O(n2 )
• Prim’s runs in O((n+m) log n)
• Kruskal runs in O(m log m) = O(m log n)
• In practice, Kruskal has a tendency to run faster
since graphs might not be dense and not all edges
need to be looked at in the Deletemin operations

09/16/2023 CSE 373 AU 04 - Minimum Spanning Trees 31

 Exercise
• Use both Prim’s and Kruskal’s algorithm and find the
minimum cost spanning tree for the following graph.
• Real life examples of • Design question: how
MST. would you implement an
• We want to connect algorithm to find the
phone lines to houses, MST of some graph,
but laying down cable assuming the edges all
is expensive. How can have the same weight?
we minimize the
amount of wire we must
install?
 Shortest Paths
• Graphs may be used to represent the highway structure of a
state or country with vertices representing cities and edges
representing sections of highway.
• The edges may then be assigned weights which might be
either the distance between the two cities.
• A motorist wishing to drive from city A to city B would be
interested in answers to the following questions:
• (i) Is there a path from A to B?
• (ii)If there is more than one path from A to B, which is the shortest
path?
• The problems defined by (i) and (ii) are special cases
of the path problem.
• The length of a path is now defined to be the sum of
the weights of the edges on that path.
• The starting vertex of the path will be referred to as
the source and the last vertex the destination.
• Given graph G = ( V, E ), a weighting function c(e) for
the edges of G and a source vertex vo.
• The problem is to determine the shortest paths from
v0 to all the remaining vertices of G.
• It is assumed that all the weights are positive.
• Example: Consider the directed graph of Figure given
below.
• The numbers on the edges are the weights.
• If vo is the source vertex, then the shortest path from vo to
v1 is vo v2 V3 v1.
• The length of this path is 10 +15 + 20 = 45. Even though
there are three edges on this path, it is
shorter than the path vov1 which is of length 50.
• In order to formulate a greedy based algorithm to generate the
shortest paths, we must conceive of a multistage solution to the
problem and also conceive of an optimization measure.
• One possibility is to build the shortest paths one by one.
• As an optimization measure we can use the sum of
the lengths of all paths so far generated.
• In order for this measure to be minimized, each
individual path must be of minimum length.

• If it’s already constructed i shortest paths then the

next path to be constructed should be the next
shortest minimum length path.
Relax
• A common operation that is used in the
algorithms is called Relax :
when a vertex v can be reached from the
source with a certain distance, we examine
an outgoing edge, say (v,w), and check if
we can improve w Can we improve this?

• E.g., v 8
4 4 ?
2 If d(w) > d(v) + w(v, w)
s 0
11 ? d(w) = d(v) + w(v, w)
7 6
8 ? ?
1

Can we improve these?

Dijkstra’s Algorithm
Dijkstra(G, s)
For each vertex v,
Mark v as unvisited, and set d(v) = ∞ ;

Set d(s) = 0 ;
while (there is unvisited vertex) {
v = unvisited vertex with smallest d ;
Visit v, and Relax all its outgoing edges;
}
return d ;
Example
8 7
4 ∞ ∞ ∞ 9
s 11
2
4
0 ∞ 14 ∞
7 6
8 ∞ ∞ 10
∞ 1 2

Relax

8 7
4 4 ∞ ∞ 9
s 2
0
11 ∞ 4 14 ∞
7 6
8 8 ∞ ∞ 10
1 2
Example
8 7
4 4 ∞ ∞ 9
s 11
2
4
0 ∞ 14 ∞
7 6
8 8 10
1 ∞ 2 ∞

Relax

8 7
4 4 12 ∞ 9
s 2
11 4 14 ∞
0 ∞
7 6
8 8 ∞ ∞ 10
1 2
Example
8 7
4 4 12 ∞ 9
s 11
2
4
0 ∞ 14 ∞
7 6
8 8 ∞ ∞ 10
1 2

Relax

8 7
4 4 12 ∞ 9
s 2
11 15 4 14
0 ∞
7 6
8 8 9 ∞ 10
1 2
Example
8 7
4 4 12 ∞ 9
s 11
2
4
0 15 14 ∞
7 6
8 8 9 ∞ 10
1 2

Relax

8 7
4 4 12 ∞ 9
s 2
0
11 15 4 14 ∞
7 6
8 8 9 11 10
1 2
Example
8 7
4 4 12 ∞ 9
s 11
2
4
0 15 14 ∞
7 6
8 8 9 11 10
1 2

Relax

8 7
4 4 12 25 9
s 2
0
11 15 4 14 21
7 6
8 8 9 11 10
1 2
Example
8 7
4 4 12 25 9
s 11
2
4
0 15 14 21
7 6
8 8 9 11 10
1 2

Relax

8 7
4 4 12 19 9
s 2
0
11 14 4 14 21
7 6
8 8 9 11 10
1 2
Example
8 7
4 4 12 19 9
s 11
2
4
0 14 14 21
7 6
8 8 9 11 10
1 2

Relax

8 7
4 4 12 19 9
s 11 2
4
0 14 14 21
7 6
8 8 9 11 10
1 2
Example
8 7
4 4 12 19 9
s 11
2
4
0 14 14 21
7 6
8 8 9 11 10
1 2

Relax

8 7
4 4 12 19 9
s 11 2
4
0 14 14 21
7 6
8 8 9 11 10
1 2
Example
8 7
4 4 12 19 9
s 11
2
4
0 14 14 21
7 6
8 8 9 11 10
1 2

Relax

8 7
4 4 12 19 9
s 11 2
4
0 14 14 21
7 6
8 8 9 11 10
1 2
Correctness
Theorem:
The kth vertex closest to the source s is
selected at the kth step inside the while
loop of Dijkstra’s algorithm
Also, by the time a vertex v is selected,
d(v) will store the length of the shortest
path from s to v

How to prove ? (By induction)

Proof
• Both statements are true for k = 1 ;
• Let vj = jth closest vertex from s
• Now, suppose both statements are true
for k = 1, 2, …, r-1
• Consider the rth closest vertex vr
• If there is no path from s to vr

 d(vr) = ∞ is never changed

• Else, there must be a shortest path
from s to vr ; Let vt be the vertex
immediately before vr in this path
Proof (cont)
• Then, we have t  r-1 (why??)
 d(vr) is set correctly once vt is selected,
and the edge (vt,vr) is relaxed (why??)
 After that, d(vr) is fixed (why??)

 d(vr) is correct when vr is selected ;

also, vr must be selected at the rth step,
because no unvisited nodes can have a
smaller d value at that time
Thus, the proof of inductive case completes
Performance
• Dijkstra’s algorithm is similar to Prim’s
• By using Fibonacci Heap,
• Relax  Decrease-Key
• Pick vertex  Extract-Min
• Running Time:
• the amortized cost of each |V|
operation O(n)
• At most O(n) Decrease-Key
 Total Time: O(n * n)
Finding Shortest Path in DAG
We have a faster algorithm for DAG :
DAG-Shortest-Path(G, s)
Topological Sort G ;
For each v, set d(v) =  ; Set d(s) = 0 ;
for (k = 1 to |V|) {
v = kth vertex in topological order ;
Relax all outgoing edges of v ;
}
return d ;
Example
s 3
4
2
11
5 6
8

Topological
Sort
11

s 6
4 3 2

8
Example
11

s 6
4 3 2
 0    

5
Process 8
this node
Relax

11

s 6
4 3 2
 0    

8
Example
11

s 6
4 3 2
 0    

5
Process 8
this node
Relax

11

s 6
4 3 2
 0 3   11

8
Example
11

s 6
4 3 2
 0 3   11

5
Process 8
this node
Relax

11

s 6
4 3 2
 0 3 5  11

8
Example
11

s 6
4 3 2
 0 3 5  11

5
Process 8
this node
Relax

11

s 6
4 3 2
 0 3 5 11 10

8
Example
11

s 6
4 3 2
 0 3 5 11 10

8
Process
Relax this node

11

s 6
4 3 2
 0 3 5 11 10

8
Example
11

s 6
4 3 2
 0 3 5 11 10

8
Process
Relax this node

11

s 6
4 3 2
 0 3 5 11 10

8
Correctness
Theorem:
By the time a vertex v is selected,
d(v) will store the length of the shortest
path from s to v

How to prove ? (By induction)

Proof
• Let vj = jth vertex in the topological order
• We will show that d(vk) is set correctly
when vk is selected, for k = 1,2, …, |V|
• When k = 1,
vk = v1 = leftmost vertex
If it is the source, d(vk) = 0
If it is not the source, d(vk) = 
 In both cases, d(vk) is correct (why?)

 Base case is correct

Proof (cont)
• Now, suppose the statement is true for
k = 1, 2, …, r-1
• Consider the vertex vr
• If there is no path from s to vr

 d(vr) =  is never changed

• Else, we shall use similar arguments as
proving the correctness of Dijkstra’s
algorithm …
Proof (cont)
• First, let vt be the vertex immediately
before vr in the shortest path from s to vr
 t  r-1
 d(vr) is set correctly once vt is
selected, and the edge (vt,vr) is relaxed
 After that, d(vr) is fixed
 d(vr) is correct when vr is selected

Thus, the proof of inductive case completes

Performance
• DAG-Shortest-Path selects vertex
sequentially according to topological order
• no need to perform Extract-Min
• We can store the d values of the vertices
in a single array  Relax takes O(1) time
• Running Time:
• Topological sort : O(V + E) time
• O(V) select, O(E) Relax : O(V + E) time
 Total Time: O(V + E)
Handling Negative Weight Edges
• When a graph has negative weight edges,
shortest path may not be well-defined

E.g., v -7
4

s 11
What is the shortest
-7
8 path from s to v?
Handling Negative Weight Edges
• The problem is due to the presence of a
cycle C, reachable by the source, whose
total weight is negative
 C is called a negative-weight cycle
• How to handle negative-weight edges ??
 if input graph is known to be a DAG,
DAG-Shortest-Path is still correct
 For the general case, we can use
Bellman-Ford algorithm
Bellman-Ford Algorithm
Bellman-Ford(G, s) // runs in O(VE) time

For each v, set d(v) =  ; Set d(s) = 0 ;

for (k = 1 to |V|-1)
Relax all edges in G in any order ;
/* check if s reaches a neg-weight cycle */
for each edge (u,v),
if (d(v) > d(u) + weight(u,v))
return “something wrong !!” ;
return d ;
Example 1
8 8
4 ∞ ∞ 4 4 ∞
s 0 3 -7 10 s 0 3 -7 10

8 ∞ ∞ Relax all 8 8 ∞
-2

Relax all
8 8
4 4 0 Relax all 4 4 1

s 0 3 -7 10 s 0 3 -7 10

8 -2
11 8
7 7 ∞
-2 -2
Example 1
After the 4th Relax all

8
4 4 0

s 0 3 -7 10

8 7 10
-2

After checking, we found that there is

nothing wrong  distances are correct
Example 2
8 8
4 ∞ ∞ 4 4 ∞
s 0 3 -7 1 s 0 3 -7 1

8 ∞ ∞ Relax all 8 8 ∞
-2 -2

Relax all
8 8
4 1 -7 Relax all 4 4 1

s 0 3 -7 1 s 0 3 -7 1

8 8
0 2 7 ∞
-2 -2
Example 2
After the 4th Relax all
This edge shows
8 something must
4 -7 -15
be wrong …
s 0 3 -7 1

8 -8 -6
-2

After checking, we found that something

must be wrong  distances are incorrect
Exercise
Run Bellman-Ford algorithm for the following graph, provided
by
E = {(S,A),(S,G),(A,E),(B,A),(B,C),(C,D),(D,E),(E,B),(F,A),(F,E),(G,F)}