Algorithmic Foundations COMP108
Greedy methods
Learning outcomes Understand
Algorithmic Foundations COMP108
what greedy method is
Able
to apply Kruskal’s algorithm to find minimum spanning tree
Able
to apply Dijkstra’s algorithm to find single-source shortest-paths
Able
to apply greedy algorithm to find solution for Knapsack problem 2 (Greedy)
Learning outcomes Understand
Algorithmic Foundations COMP108
what greedy method is
Able
to apply Kruskal’s algorithm to find minimum spanning tree
Able
to apply Dijkstra’s algorithm to find single-source shortest-paths
Able
to apply greedy algorithm to find solution for Knapsack problem 3 (Greedy)
Greedy methods
Algorithmic Foundations COMP108
How to be greedy? At
every step, make the best move you can make.
Keep
going until you’re done
Advantages Don’t
need to pay much effort at each step.
Usually The
finds a solution very quickly.
solution found is usually not bad.
Possible problem The
solution found may NOT be the best one
4 (Greedy)
Algorithmic Foundations COMP108
Greedy methods - examples Minimum spanning tree Kruskal’s
algorithm
Single-source shortest-paths Dijkstra’s
algorithm
Both algorithms find (one of) the BEST solution Knapsack problem greedy
algorithm does NOT find the BEST solution 5 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm …
Learning outcomes Understand
Algorithmic Foundations COMP108
what greedy method is
Able
to apply Kruskal’s algorithm to find minimum spanning tree
Able
to apply Dijkstra’s algorithm to find single-source shortest-paths
Able
to apply greedy algorithm to find solution for Knapsack problem 7 (Greedy)
Algorithmic Foundations COMP108
Minimum Spanning tree (MST) Given an undirected connected graph G The
edges are labelled by weight
Spanning tree of G a
tree containing all vertices in G
Minimum spanning tree a
spanning tree of G with minimum weight
8 (Greedy)
Algorithmic Foundations COMP108
Examples Graph G (edge label is weight)
a 2
3
c
3
b 2
d
1
Spanning trees of G a c
2 1
b 2
d
a 3
c
2
b 2
d
a
3
3
c
1
b d
MST 9 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
e f
Arrange the edges from smallest to largest weight
10
10 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
e f
10
Choose the minimum weight edge 11 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
e f
10
Choose the next minimum weight edge 12 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
e f
10
Continue as long as no cycle forms 13 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
e f
10
Continue as long as no cycle forms 14 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
e f
10
Continue as long as no cycle forms 15 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
e f
10
Continue as long as no cycle forms 16 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
f
e 10
(h,i) cannot be included, otherwise, a cycle is formed
17 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
f
e 10
Choose the next minimum weight edge 18 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
f
e 10
(a,h) cannot be included, otherwise, a cycle is formed
19 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
f
e 10
Choose the next minimum weight edge 20 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
f
e 10
(f,e) cannot be included, otherwise, a cycle is formed
21 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
f
e 10
(b,h) cannot be included, otherwise, a cycle is formed
22 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
f
e 10
(d,f) cannot be included, otherwise, a cycle is formed
23 (Greedy)
Algorithmic Foundations COMP108
Kruskal’s algorithm - MST (h,g)
1
(i,c)
2
(g,f)
2
(a,b)
4
(c,f)
4
(c,d)
7
(h,i)
7
(b,c)
8
(a,h)
8
(d,e)
9
(f,e)
10
(b,h)
11
(d,f)
14
8
b
4
c
d
2 11
a
7
7
8 h
4
i
1
g
9
14
2
f
MST is found when all edges are examined
e 10
24 (Greedy)
Kruskal’s algorithm - MST
Algorithmic Foundations COMP108
Kruskal’s algorithm is greedy in the sense that it always attempt to select the smallest weight edge to be included in the MST
25 (Greedy)
Algorithmic Foundations COMP108
Exercise – Find MST for this graph 4
b
4
3
10 3
a
c
6
10
d
6 f
4
e
5
26 (Greedy)
Algorithmic Foundations COMP108
Exercise – Find MST for this graph 4
b
4
3
10 3
a
c
6
10
d
6 f
4
e
5
order of selection: (b,f), (c,f), (a,b), (f,e), (e,d) 27 (Greedy)
Algorithmic Foundations COMP108
Pseudo code
// Given an undirected connected graph G=(V,E) pick an edge e in E with minimum weight T = { e } and E’ = E – { e } while E’ ≠ ∅ do
Time complexity?
begin
O(nm)
pick an edge e in E’ with minimum weight if adding e to T does not form cycle then T=T∪ {e} E’ = E’ – { e } end
Can be tested by marking vertices 28 (Greedy)
Learning outcomes Understand
Algorithmic Foundations COMP108
what greedy method is
Able
to apply Kruskal’s algorithm to find minimum spanning tree
Able
to apply Dijkstra’s algorithm to find single-source shortest-paths
Able
to apply greedy algorithm to find solution for Knapsack problem 29 (Greedy)
Algorithmic Foundations COMP108
Dijkstra’s algorithm …
Algorithmic Foundations COMP108
Single-source shortest-paths
Consider a (un)directed connected graph G The
edges are labelled by weight
Given a particular vertex called the source Find
shortest paths from the source to all other vertices (shortest path means the total weight of the path is the smallest)
31 (Greedy)
Algorithmic Foundations COMP108
Example Directed Graph G (edge label is weight) a is source node
a
5
c
a c
5
2
e d
2
2
5
2 2
b
5
b
5
5
e d
2
thick lines: shortest path dotted lines: not in shortest path
32 (Greedy)
Algorithmic Foundations COMP108
Single-source shortest paths vs MST Shortest paths from a
a
5
b
5
c
a
5
b
5
c
2 2
5
e d 2
2 2
5
e d 2
What is the difference between MST and shortest paths from a?
MST 33 (Greedy)
Algorithmic Foundations COMP108
Algorithms for shortest paths Algorithms there
are many algorithms to solve this problem, one of them is Dijkstra’s algorithm, which assumes the weights of edges are non-negative
34 (Greedy)
Dijkstra’s algorithm
Algorithmic Foundations COMP108
Input: A directed connected weighted graph G and a source vertex s Output: For every vertex v in G, find the shortest path from s to v Dijkstra’s algorithm runs in iterations: in
the i-th iteration, the vertex which is the i-th closest to s is found,
for
every remaining vertices, the current shortest path to s found so far (this shortest path will be updated as the algorithm runs)
35
(Greedy)
Algorithmic Foundations COMP108
Dijkstra’s algorithm
Suppose vertex a is the source, we now show how Dijkstra’s algorithm works
9 a
24
b
h
18
14
c
15
5 d
6
2 30
11
e
16
20 44
f
19 6 k 36 (Greedy)
Algorithmic Foundations COMP108
Dijkstra’s algorithm
Every vertex v keeps 2 labels: (1) the weight of the current shortest path from a; (2) the vertex leading to v on that path, initially as (∞ , -) b
9 a
c
15
5 d
20
(∞ , -)
24
(∞ , -)
14
(∞ , -)
(∞ , -)
h
18
6
2 30
11
e (∞ , -)
f (∞ , -)
16 44
19 6 k (∞ , -)37 (Greedy)
Algorithmic Foundations COMP108
Dijkstra’s algorithm
For every neighbor u of a, update the weight to the weight of (a,u) and the leading vertex to a. Choose the one with the smallest such weight. chosen
b
9 a
c
15
new values
24
(14, (∞ , -) a)
14
(∞ , -) (15, a)
(∞ , -)
(∞ (9,, a) -)
5
h
18
6
2 30
20
d being considered
11
e (∞ , -)
f (∞ , -)
16 44
shortest path
19 6 k (∞ , -)38 (Greedy)
Algorithmic Foundations COMP108
Dijkstra’s algorithm
For every un-chosen neighbor of vertex b, update the weight and leading vertex. Choose among all un-chosen vertices the one with smallest weight. b
9 a
14 15
(33, (∞ , b) -)
(9, a)
24
(14, a) c
chosen 5
18
6
2 30
20
(15, a) d new values
h
being considered
11
e (∞ , -)
f (∞ , -)
16 44
shortest path
19 6 k (∞ , -)39 (Greedy)
Algorithmic Foundations COMP108
Dijkstra’s algorithm
If a new path with smallest weight is discovered, e.g., for vertex h, the weight is updated. Otherwise, like vertex d, no update. b
9 a
14 15
24
(14, a) c 5
chosen
(33, (32, b) c)
(9, a)
18
6
2 30
20
(15, a) d new values
h
being considered
11
e (∞ (44, , -)c)
f (∞ , -)
16 44
shortest path
19 6 k (∞ , -)40 (Greedy)
Algorithmic Foundations COMP108
Dijkstra’s algorithm
Repeat the procedure. After d is chosen, the weight of e and k is updated. Next vertex chosen is h. b
9 a
14 15
chosen
(9, a)
24
(14, a) c 5
h
18
6
2 30
20
(15, a) d new values
(32, c)
being considered
11
e (44, (35, c) d)
f (∞ , -)
16 44
shortest path
19 6 k (59, (∞ , -) d)41 (Greedy)
Algorithmic Foundations COMP108
Dijkstra’s algorithm
After h is chosen, the weight of e and k is updated again. Next vertex chosen is e. b
9 a
14 15
(32, c)
(9, a)
24
(14, a) c 5
30
20
(15, a) d new values
being considered
h
18 chosen
11
e (35, (34, d) h)
6
2 f (∞ , -)
16 44
shortest path
19 6 k (51, (59,d) h)42 (Greedy)
Algorithmic Foundations COMP108
Dijkstra’s algorithm
After e is chosen, the weight of f and k is updated again. Next vertex chosen is f. b
9 a
14 15
(32, c)
(9, a)
24
(14, a) c 5
30
20
(15, a) d new values
being considered
h
18 2 chosen f 11 (45, (∞ , -) e)
e (34, h)
16 44
shortest path
6 19 6 k (51, (50, h) e)43 (Greedy)
Algorithmic Foundations COMP108
Dijkstra’s algorithm
After f is chosen, it is NOT necessary to update the weight of k. The final vertex chosen is k. b
9 a
14 15
(32, c)
(9, a)
24
(14, a) c 5
18
6
2 30
20
(15, a) d new values
h
being considered
11
e (34, h)
f (45, e)
16 44
shortest path
19 6 k
chosen
(50, e)44 (Greedy)
Algorithmic Foundations COMP108
Dijkstra’s algorithm
At this point, all vertices are chosen, and the shortest path from a to every vertex is discovered. b
9 a
14 15
(32, c)
(9, a)
24
(14, a) c 5
18
6
2 30
20
(15, a) d new values
h
being considered
11
e (34, h)
f (45, e)
16 44
shortest path
19 6 k (50, e)45 (Greedy)
Algorithmic Foundations COMP108
Exercise – Shortest paths from a 4
b
4
3
10 3
a
c
6
10
d
6 f
4
e
5
46 (Greedy)
Algorithmic Foundations COMP108
Exercise – Shortest paths from a (4,a) (∞ ,-)
(8,b) 4
b
4
c
3
10 3
a
(∞ ,-) 6
10
6 f (∞ ,-)
4
(6,a) order of selection: (a,b), (a,f), (b,c), (f,e), (c,d)
e (∞ ,-)
(14,c) d
(∞ ,-)
5
(14,b) (10,f)
Compare the solution with slide #28
47 (Greedy)
Dijkstra’s algorithm
Algorithmic Foundations COMP108
To describe the algorithm using pseudo code, we give some notations. Each vertex v is labelled with two labels: numeric label d(v) indicates the length of the shortest path from the source to v found so far
a
label p(v) indicates next-to-last vertex on such path, i.e., the vertex immediately before v on that shortest path
another
48 (Greedy)
Algorithmic Foundations COMP108
Pseudo code // Given a graph G=(V,E) and a source vertex s for every vertex v in the graph do
Time complexity?
set d(v) = ∞ and p(v) = null set d(s) = 0 and VT = ∅ while V - VT ≠ ∅ do
O(n2) // there is still some vertex left
begin choose the vertex u in V - VT with minimum d(u) set VT = VT ∪ { u } for every vertex v in V - VT that is a neighbour of u do if d(u) + w(u,v) < d(v) then
// a shorter path is found
set d(v) = d(u) + w(u,v) and p(v) = u end
49 (Greedy)
Algorithmic Foundations COMP108
Does Greedy algorithm always return the best solution?
Knapsack Problem
Algorithmic Foundations COMP108
Input: Given n items with weights w1, w2, …, wn and values v1, v2, …, vn, and a knapsack with capacity W. Output: Find the most valuable subset of items that can fit into the knapsack. Application: A transport plane is to deliver the most valuable set of items to a remote location without exceeding its capacity. 51 (Greedy)
Algorithmic Foundations COMP108
Example 1
capacity = 50 w = 10 v = 60 item 1 subset
φ {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}
w = 20 v = 100 item 2 total weight
0 10 20 30 30 40 50 60
w = 30 v = 120 item 3
total value
0 60 100 120 160 180 220 N/A
knapsack
52 (Greedy)
Algorithmic Foundations COMP108
Greedy approach
capacity = 50 w = 10 v = 60 item 1
w = 20 v = 100 item 2
w = 30 v = 120 item 3
knapsack
Greedy: pick the item with the next largest value if total weight <= capacity. Result:
item 3 is taken, total value = 120, total weight = 30 item 2 is taken, total value = 220, total weight = 50 item 1 cannot be taken Does this always work?
53 (Greedy)
Algorithmic Foundations COMP108
Example 2
capacity = 10 w=7 v = 42 item 1 subset
φ {1} {2} {3} {4} {1,2} {1,3} {1,4}
w=3 v = 12 item 2
total weight
0 7 3 4 5 10 11 12
w=4 v = 40 item 3
total value
0 42 12 40 25 54 N/A N/A
w=5 v = 25 item 4 subset
knapsack
total weight
{2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
7 8 9 14 15 16 12 19
total value
52 37 65 N/A N/A N/A N/A N/A
54 (Greedy)
Algorithmic Foundations COMP108
Greedy approach
capacity = 10 w=7 v = 42 item 1
w=3 v = 12 item 2
w=4 v = 40 item 3
w=5 v = 25 item 4
knapsack
Greedy: pick the item with the next largest value if total weight <= capacity. Result:
item 1 is taken, total value = 42, total weight = 7 not the item 3 cannot be taken best!! item 4 cannot be taken item 2 is taken, total value = 54, total weight = 10
55
(Greedy)
Algorithmic Foundations COMP108
Greedy approach 2 v/w = 6
v/w = 4 v/w = 10 v/w = 5
w=7 v = 42 item 1
w=3 v = 12 item 2
w=4 v = 40 item 3
w=5 v = 25 item 4
capacity = 10
knapsack
Greedy 2: pick the item with the next largest value/weight if total weight <= capacity. Result:
item 3 is taken, total value = 40, total weight = 4 item 1 cannot be taken item 4 is taken, total value = 65, total weight = 9 item 2 cannot be taken
Also work for Example 1?
56 (Greedy)
Algorithmic Foundations COMP108
Greedy approach 2 v/w = 6
v/w=5
v/w = 4
w = 10 v = 60 item 1
w = 20 v = 100 item 2
w = 30 v = 120 item 3
capacity = 50
knapsack
Greedy: pick the item with the next largest value/weight if total weight <= capacity. Result:
item 1 is taken, total value = 60, total weight = 10 item 2 is taken, total value = 160, total weight = 30 item 3 cannot be taken Not the best!!
57 (Greedy)
Algorithmic Foundations COMP108
Lesson Learned: Greedy algorithm does NOT always return the best solution
Learning outcomes Understand
Algorithmic Foundations COMP108
what greedy method is
Able
to apply Kruskal’s algorithm to find minimum spanning tree
Able
to apply Dijkstra’s algorithm to find single-source shortest-paths
Able
to apply greedy algorithm to find solution for Knapsack problem 59 (Greedy)