COMP90038 Algorithms and Complexity
COMP90038
Algorithms and Complexity
Lecture 20: Greedy Algorithms – Prim and Dijkstra
(with thanks to Harald Søndergaard & Michael Kirley)
Andres Munoz-Acosta
munoz.m@unimelb.edu.au
Peter Hall Building G.83
mailto:munoz.m@unimelb.edu.au
Recap
• We have talked a lot about dynamic programming:
• DP is bottom-up problem solving technique.
• Similar to divide-and-conquer; however, problems are overlapping, making
tabulation a requirement.
• Solutions often involve recursion.
• We applied this idea to two graph problems:
• Computing the transitive closure of a directed graph; and
• Finding shortest distances in weighted directed graphs.
A practice challenge
• Can you solve the problem in the
figure?
• W = 15
• w = [1 1 2 4 12]
• v = [1 2 2 10 4]
• Because it is a larger instance,
memoing is preferable.
• How many states do we need to
evaluate?
• FYI the answer is $15 {1,2,3,4}
The table
j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
w v i
0
1 1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 1 1 1 1
1 2 2 2 -1 3 -1 -1 -1 -1 -1 3 -1 3 -1 3 -1 3
2 2 3 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 5 -1 -1 -1 5
4 10 4 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 15
12 4 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 15
• We know that we include all the elements up to 4 because the last column (15) is
the cumulative sum of the values.
Warshall’s algorithm
• Warshall’s algorithm computes the transitive closure of
a directed graph.
• An edge (a,d) is in the transitive closure of graph G iff there is
a path in G from a to d.
• Is there a path from node i to node j using nodes [1 …
k] as “stepping stones”?
• Such path will exist if and only if we can:
• step from i to j using only nodes [1 … k-1], or
• step from i to k using only nodes [1 … k-1], and then step
from k to j using only nodes [1 … k-1].
a b
c d
Warshall’s algorithm
• Warshall’s algorithm computes the transitive closure of
a directed graph.
• An edge (a,d) is in the transitive closure of graph G iff there is
a path in G from a to d.
• Is there a path from node i to node j using nodes [1 …
k] as “stepping stones”?
• Such path will exist if and only if we can:
• step from i to j using only nodes [1 … k-1], or
• step from i to k using only nodes [1 … k-1], and then step
from k to j using only nodes [1 … k-1].
a b
c d
Warshall’s Algorithm
• If G’s adjacency matrix is A then we can express the recurrence
relation as:
• We examined the simplest version of the algorithm.
Warshall’s Algorithm
• Let’s visualize the steps.
• Using node 2 (k=2), we can
reach node 3 from nodes 1 and
5.
1
2
5 3
47
6
1
2
5 3
47
6
Warshall’s Algorithm
• Let’s visualize the steps.
• Using node 2 (k=2), we can
reach node 3 from nodes 1 and
5.
1
2
5 3
47
6
1
2
5 3
47
6
Warshall’s Algorithm
• Let’s visualize the steps.
• Using node 2 (k=2), we can
reach node 3 from nodes 1 and
5.
• Using node 3 (k=3) we can
reach: Nodes [6 7] from nodes
[1,2,5]
1
2
5 3
47
6
1
2
5 3
47
6
Floyd’s Algorithm
• Floyd’s algorithm solves the all-pairs shortest-path
problem for weighted graphs with positive weights.
• It works for directed as well as undirected graphs.
• What is the shortest path from node i to node j using
nodes [1 … k] as “stepping stones”?
• Such path will exist if and only if we can:
• step from i to j using only nodes [1 … k-1], or
• step from i to k using only nodes [1 … k-1], and then step from k
to j using only nodes [1 … k-1].
a b
c d
3
1 2
5
3
Floyd’s Algorithm
• Floyd’s algorithm solves the all-pairs shortest-path
problem for weighted graphs with positive weights.
• It works for directed as well as undirected graphs.
• What is the shortest path from node i to node j using
nodes [1 … k] as “stepping stones”?
• Such path will exist if and only if we can:
• step from i to j using only nodes [1 … k-1], or
• step from i to k using only nodes [1 … k-1], and then step from k
to j using only nodes [1 … k-1].
a b
c d
3
1 2
5
3
Floyd’s Algorithm
• If G’s weight matrix is W then we can express the recurrence relation
as:
• A simpler version updating D:
Floyd’s Algorithm
• For k=2
• We can go 1 → 2 → 3, the distance
1 → 3 is 9 + 5 = 14
• We can go 5 → 2 → 3, the distance
of 5 → 3 is 4 + 5 = 9
1
2
5 3
47
6
9
7
4
5
6
2
6
7
6
4
7
Floyd’s Algorithm
• For k=2
• We can go 1 → 2 → 3, the distance
1 → 3 is 9 + 5 = 14
• We can go 5 → 2 → 3, the distance
of 5 → 3 is 4 + 5 = 9
• The distance matrix gets
updated to:
1
2
5 3
47
6
9
7
4
5
6
2
6
7
6
4
7
Greedy Algorithms
• A problem solving strategy is to take the locally best choice among all
feasible ones.
• Once we do this, our decision is irrevocable.
• We want to change 30 cents using the smallest number of coins.
• If we assume coin denominations of {25, 10, 5, 1}, we could use as many 25-
cent pieces as we can, then do the same for 10-cent pieces, and so on, until
we have reached 30 cents (25+5).
• This greedy strategy would not work for denominations {25, 10, 1}
(25+1+1+1+1+1 compared to 10+10+10).
Greedy Algorithms
• In general, it is unusual that locally best choices yield global best
results.
• However, there are problems for which a greedy algorithm is correct and
fast.
• In some other problems, a greedy algorithm serve as an acceptable
approximation algorithm.
• Here we shall look at:
• Prim’s algorithm for finding minimum spanning trees
• Dijkstra’s algorithm for single-source shortest paths
What is an Spanning Tree?
• Recall that a tree is a connected graph with no cycles.
• A spanning tree of a graph V,E is a tree V,E’ where E’ is a subset of
E
• For example, the graph on the left has eight different spanning trees:
a c
b d
e
f
6 5
42
42
5
314
Minimum Spanning Trees of Weighted Graphs
• For a weighted graph, some spanning trees are more desirable than
others.
• For example, suppose we have a set of “stations” to connect in a network, and also
some possible connections, each with its own cost.
• This is the problem of finding a spanning tree with the smallest possible
cost.
• Such tree is a minimum spanning tree for the graph.
a c
b d
e
f
6 5
42
42
5
314
Minimum Spanning Trees of Weighted Graphs
• For a weighted graph, some spanning trees are more desirable than
others.
• For example, suppose we have a set of “stations” to connect in a network, and also
some possible connections, each with its own cost.
• This is the problem of finding a spanning tree with the smallest possible
cost.
• Such tree is a minimum spanning tree for the graph.
Prim’s Algorithm
• Prim’s algorithm is an example of a greedy algorithm.
• It constructs a sequence of subtrees T, by adding to the latest tree the
closest node not currently on it.
• A simple version:
Prim’s Algorithm
• But how to find the minimum-weight edge (v,u)?
• A standard way to do this is to organise the nodes that are not yet
included in the spanning tree T as a priority queue, organised in a
min-heap by edge cost.
• The information about which nodes are connected in T can be
captured by an array prev of nodes, indexed by V. Namely, when (v,u)
is included, this is captured by setting prev[u] = v.
Prim’s Algorithm
• The complete algorithm is:
Prim’s Algorithm
• On the first loop, we only create the table
a c
b d
e
f
6 5
42
42
5
314
Tree T a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 5 6 4
prev a a a nil nil
a,d
cost 2 2 4
prev d d nil d
a,d,b
cost 1 4
prev b nil d
a,d,b,c
cost 5 3
prev c c
a,d,b,c,f
cost 4
prev f
a,d,b,c,f,e
cost
prev
Prim’s Algorithm
a c
b d
e
f
6 5
42
42
5
314
Tree T a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 5 6 4
prev a a a nil nil
a,d
cost 2 2 4
prev d d nil d
a,d,b
cost 1 4
prev b nil d
a,d,b,c
cost 5 3
prev c c
a,d,b,c,f
cost 4
prev f
a,d,b,c,f,e
cost
prev
• Then we pick the first node as the initial one
Prim’s Algorithm
a c
b d
e
f
6 5
42
42
5
314
Tree T a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 5 6 4
prev a a a nil nil
a,d
cost 2 2 4
prev d d nil d
a,d,b
cost 1 4
prev b nil d
a,d,b,c
cost 5 3
prev c c
a,d,b,c,f
cost 4
prev f
a,d,b,c,f,e
cost
prev
• We take the first node out of the queue and update
the costs
Prim’s Algorithm
a c
b d
e
f
6 5
42
42
5
314
Tree T a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 5 6 4
prev a a a nil nil
a,d
cost 2 2 4
prev d d nil d
a,d,b
cost 1 4
prev b nil d
a,d,b,c
cost 5 3
prev c c
a,d,b,c,f
cost 4
prev f
a,d,b,c,f,e
cost
prev
• We eject the node with the lowest cost and update
the queue.
Prim’s Algorithm
a c
b d
e
f
6 5
42
42
5
314
Tree T a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 5 6 4
prev a a a nil nil
a,d
cost 2 2 4
prev d d nil d
a,d,b
cost 1 4
prev b nil d
a,d,b,c
cost 5 3
prev c c
a,d,b,c,f
cost 4
prev f
a,d,b,c,f,e
cost
prev
• We eject the next node based on alphabetical order.
Why is f not updated?
Prim’s Algorithm
a c
b d
e
f
6 5
42
42
5
314
Tree T a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 5 6 4
prev a a a nil nil
a,d
cost 2 2 4
prev d d nil d
a,d,b
cost 1 4
prev b nil d
a,d,b,c
cost 5 3
prev c c
a,d,b,c,f
cost 4
prev f
a,d,b,c,f,e
cost
prev
• We now update f
Prim’s Algorithm
a c
b d
e
f
6 5
42
42
5
314
Tree T a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 5 6 4
prev a a a nil nil
a,d
cost 2 2 4
prev d d nil d
a,d,b
cost 1 4
prev b nil d
a,d,b,c
cost 5 3
prev c c
a,d,b,c,f
cost 4
prev f
a,d,b,c,f,e
cost
prev
• We reach the last choice
Prim’s Algorithm
a c
b d
e
f
6 5
42
42
5
314
Tree T a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 5 6 4
prev a a a nil nil
a,d
cost 2 2 4
prev d d nil d
a,d,b
cost 1 4
prev b nil d
a,d,b,c
cost 5 3
prev c c
a,d,b,c,f
cost 4
prev f
a,d,b,c,f,e
cost
prev
• The resulting tree is {a,d,b,c,f,e}
Analysis of Prim’s Algorithm
• First, a crude analysis: For each node, we look through the edges to find
those incident to the node, and pick the one with smallest cost. Thus we
get O(|V||E|). However, we are using cleverer data structures.
• Using adjacency lists for the graph and a min-heap for the priority queue,
we perform |V| – 1 heap deletions (each at cost O(log |V|)) and |E|
updates of priorities (each at cost O(log |V|)).
• Altogether (|V|-1+|E|) O(log |V|).
• Since, in a connected graph, |V|-1 |E|, this is O(|E| log |V|).
Dijkstra’s Algorithm
• Another classical greedy weighted-graph algorithm is Dijkstra’s
algorithm, whose overall structure is the same as Prim’s.
• Recall that Floyd’s algorithm gave us the shortest paths, for every pair
of nodes, in a (directed or undirected) weighted graph. It assumed an
adjacency matrix representation and had complexity O(|V|3).
• Dijkstra’s algorithm is also a shortest-path algorithm for (directed or
undirected) weighted graphs. It finds all shortest paths from a fixed
start node. Its complexity is the same as that of Prim’s algorithm.
Dijkstra’s Algorithm
• The complete algorithm is:
Dijkstra’s Algorithm
• On the first loop, we only create the table
a c
b d
e
f
4 2
11
52
1
3
1
Covered a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost ¥ 4 1
prev nil a a nil nil
a,d
cost 3 2 5 6
prev d d d d
a,d,c
cost 3 4 5
prev d c c
a,d,c,b
cost 4 5
prev c c
a,d,c,b,e
cost 5
prev c
a,d,c,b,e,f
cost
prev
4
Dijkstra’s Algorithm
• Then we pick the first node as the initial one
a c
b d
e
f
4 2
11
52
1
3
1
Covered a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost ¥ 4 1
prev nil a a nil nil
a,d
cost 3 2 5 6
prev d d d d
a,d,c
cost 3 4 5
prev d c c
a,d,c,b
cost 4 5
prev c c
a,d,c,b,e
cost 5
prev c
a,d,c,b,e,f
cost
prev
4
Dijkstra’s Algorithm
• Then we pick the first node as the initial one
a c
b d
e
f
4 2
11
52
1
3
1
Covered a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 4 1
prev nil a a nil nil
a,d
cost 3 2 5 6
prev d d d d
a,d,c
cost 3 4 5
prev d c c
a,d,c,b
cost 4 5
prev c c
a,d,c,b,e
cost 5
prev c
a,d,c,b,e,f
cost
prev
4
Dijkstra’s Algorithm
• Then eject the node with the shortest distance from the
queue. Then, we update all the paths by adding 1.
a c
b d
e
f
4 2
11
52
1
3
1
Covered a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 4 1
prev nil a a nil nil
a,d
cost 3 2 5 6
prev d d d d
a,d,c
cost 3 4 5
prev d c c
a,d,c,b
cost 4 5
prev c c
a,d,c,b,e
cost 5
prev c
a,d,c,b,e,f
cost
prev
4
Dijkstra’s Algorithm
• Our next node will be the one with the shortest path
in overall (b)
a c
b d
e
f
4 2
11
52
1
3
1
Covered a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 4 1
prev nil a a nil nil
a,d
cost 3 2 5 6
prev d d d d
a,d,c
cost 3 4 5
prev d c c
a,d,c,b
cost 4 5
prev c c
a,d,c,b,e
cost 5
prev c
a,d,c,b,e,f
cost
prev
4
Dijkstra’s Algorithm
• Now, we continue evaluating from (c)
a c
b d
e
f
4 2
11
52
1
3
1
Covered a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 4 1
prev nil a a nil nil
a,d
cost 3 2 5 6
prev d d d d
a,d,c
cost 3 4 5
prev d c c
a,d,c,b
cost 4 5
prev c c
a,d,c,b,e
cost 5
prev c
a,d,c,b,e,f
cost
prev
4
Dijkstra’s Algorithm
• We arrive at our last decision.
a c
b d
e
f
4 2
11
52
1
3
1
Covered a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 4 1
prev nil a a nil nil
a,d
cost 3 2 5 6
prev d d d d
a,d,c
cost 3 4 5
prev d c c
a,d,c,b
cost 4 5
prev c c
a,d,c,b,e
cost 5
prev c
a,d,c,b,e,f
cost
prev
4
Dijkstra’s Algorithm
• Our complete tree is {a,d,c,b,e,f}
Covered a b c d e f
cost
prev nil nil nil nil nil nil
cost 0
prev nil nil nil nil nil nil
a
cost 4 1
prev nil a a nil nil
a,d
cost 3 2 5 6
prev d d d d
a,d,c
cost 3 4 5
prev d c c
a,d,c,b
cost 4 5
prev c c
a,d,c,b,e
cost 5
prev c
a,d,c,b,e,f
cost
prev
a c
b d
e
f
4 2
12
52
1
3
1
4
Tracing paths
• The array prev is not really needed, unless we want to retrace the
shortest paths from node a
• This tree is referred as the shortest-path tree
a c
b d
e
f
2
1
2
3
1
Spanning trees and Shortest-Path trees
• The shortest-path tree that results from Dijkstra’s algorithm is very similar
to the minima spaning tree.
• Exercise:
• Which edge is missing in the minimal spanning tree? (a,e)
• Which edge is missing from the shortest-path tree? (e,d)
• Assume that you always started from node a.
a
b
c
e d
1 3
2
22
Next lecture
• We will have a look to Huffman encoding for data compression