COMP20007 Design of Algorithms
Greedy Algorithms: Prim and Dijkstra
Lars Kulik Lecture 8 Semester 1, 2021
1
Greedy Algorithms
A natural strategy to problem solving is to make decisions based on what is the locally best choice.
Suppose we have coin denominations 25, 10, 5, and 1, and we want to change 30 cents using the smallest number of coins.
In general we will want to 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. (In this case we use 25+5 cents.)
This greedy strategy will work for the given denominations, but not for, say, 25, 10, 1.
2
Greedy Algorithms
In general we cannot expect locally best choices to yield globally best outcomes.
However, there are some well-known algorithms that rely on the greedy approach, being both correct and fast.
In other cases, for hard problems, a greedy algorithm can sometimes 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
3
The Priority Queue
A priority queue is a set (or pool) of elements.
An element is injected into the priority queue together with a priority (often the key value itself) and elements are ejected according to priority.
As an abstract data type, the priority queue supports the following operations on a “pool” of elements (ordered by some linear order):
• find an item with maximal priority
• insert a new item with associated priority • test whether a priority queue is empty
• eject the largest element
4
Stacks and Queues as Priority Queues
Special instances are obtained when we use time for priority:
• If “large” means “late” we obtain the stack. • If “large” means “early” we obtain the queue.
5
Possible Implementations of the Priority Queue
Assume priority = key.
Unsorted array or list Sorted array or list
Inject(e )
Eject()
✎
6
Spanning Trees
Recall that a tree is a connected graph with no cycle.
A spanning tree of a graph ⟨V,E⟩ is a tree ⟨V,E′⟩ with E′ ⊆ E.
The graph has eight different spanning trees:
7
Minimum Spanning Trees of Weighted Graphs
In applications where the edges correspond to distances, or cost, some spanning trees will be more desirable than others.
Suppose we have a set of ‘stations’ to connect in a network, and also some possible connections, together with the cost of each connection.
Then we have a weighted graph problem, of finding a spanning tree with the smallest possible cost.
a6c5e 541234 b2d4f
8
Minimum Spanning Trees
Given a weighted graph, a sub-graph which is a tree with minimal weight is a minimum spanning tree for the graph.
a6c5e 541234 b2d4f
9
Minimum Spanning Trees: Prim’s Algorithm
Prim’s algorithm is an example of a greedy algorithm.
It constructs a sequence of subtrees T, each adding a node together with an edge to a node in the previous subtree. In each step it picks a closest node from outside the tree and adds that. A sketch:
function Prim(⟨V , E ⟩) VT ← {v0}
ET ←∅
for i ← 1 to |V | − 1 do
findaminimum-weightedge(v,u)∈VT ×(V\VT) VT ←VT ∪{u}
ET ←ET ∪{(v,u)}
return ET
10
Prim’s Algorithm
Note that in each iteration, the tree grows by one edge.
Or, we can say that the tree grows to include the node from outside that has the smallest cost.
But how do we 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 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 .
11
Prim’s Algorithm
function Prim(⟨V , E ⟩) for each v ∈ V do
cost[v] ← ∞ prev[v] ← nil
pick initial node v0
cost[v0] ← 0
Q ← InitPriorityQueue(V ) while Q is non-empty do
u ← EjectMin(Q) foreach(u,w)∈E do
⊲ priorities are cost values
if w ∈ Q and weight(u,w) < cost[w] then
cost[w] ← weight(u,w)
prev[w] ← u
Update(Q,w,cost[w]) ⊲ rearranges priority queue
12
Prim’s Algorithm: Example
a6c5e
541234
b2d4f
TreeT abcdef
− 0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
13
Prim’s Algorithm: Example
a6c5e
541234
b2d4f
TreeT abcdef
− 0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil a 5/a 6/a 4/a ∞/nil ∞/nil
13
Prim’s Algorithm: Example
a6c5e
541234
b2d4f
TreeT abcdef
−
a a,d
0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil 5/a 6/a 4/a ∞/nil ∞/nil 2/d 2/d ∞/nil 4/d
13
Prim’s Algorithm: Example
a6c5e
541234
b2d4f
TreeT abcdef
−
a
a,d a,d,b
0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
5/a 6/a 2/d 2/d 1/b
4/a
∞/nil ∞/nil ∞/nil 4/d ∞/nil 4/d
13
Prim’s Algorithm: Example
a6c5e
541234
b2d4f
TreeT abcdef
−
a
a,d a,d,b a,d,b,c
0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
5/a 6/a 2/d 2/d 1/b
4/a
∞/nil ∞/nil ∞/nil 4/d ∞/nil 4/d
5/c 3/c
13
Prim’s Algorithm: Example
a6c5e
541234
b2d4f
TreeT abcdef
−
0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
4/a
5/a 6/a 2/d 2/d 1/b
∞/nil ∞/nil ∞/nil 4/d ∞/nil 4/d
a
a,d
a,d,b
a,d,b,c
a,d,b,c,f 4/f
5/c 3/c
13
Prim’s Algorithm: Example
a6c5e
541234
b2d4f
TreeT abcdef
−
0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
4/a
5/a 6/a 2/d 2/d 1/b
∞/nil ∞/nil ∞/nil 4/d ∞/nil 4/d
a
a,d
a,d,b
a,d,b,c
a,d,b,c,f 4/f a,d,b,c,f,e
5/c 3/c
13
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 can do better! We will discuss this later.
14
Dijkstra’s Algorithm
Another classical greedy weighted-graph algorithm is Dijkstra’s algorithm, whose overall structure is the same as Prim’s.
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.
15
Dijkstra’s Algorithm
function Dijkstra(⟨V,E⟩,v0) for each v ∈ V do
dist[v] ← ∞ prev[v] ← nil
dist[v0] ← 0
Q ← InitPriorityQueue(V ) while Q is non-empty do
u ← EjectMin(Q) foreach(u,w)∈E do
⊲ priorities are distances
if w ∈ Q and dist[u] + weight(u, w) < dist[w] then
dist[w] ← dist[u] + weight(u, w)
prev[w] ← u
Update(Q,w,dist[w]) ⊲ rearranges priority queue
16
Dijkstra’s Algorithm: Example
a4c2e 3
111 1 4
bdf
25
Covered abcdef
− 0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
17
Dijkstra’s Algorithm: Example
a4c2e 3
111 1 4
bdf
25
Covered abcdef
− 0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil a ∞/nil 4/a 1/a ∞/nil ∞/nil
17
Dijkstra’s Algorithm: Example
a4c2e 3
111 1 4
bdf
25
Covered abcdef
−
a a,d
0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil 4/a 1/a ∞/nil ∞/nil
3/d 2/d 5/d 6/d
17
Dijkstra’s Algorithm: Example
a4c2e 3
111 1 4
bdf
25
Covered abcdef
−
0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
a
a,d
a,d,c 3/d
∞/nil 4/a 3/d 2/d
1/a
∞/nil ∞/nil 5/d 6/d 4/c 5/c
17
Dijkstra’s Algorithm: Example
a4c2e 3
111 1 4
bdf
25
Covered abcdef
−
a
a,d
a,d,c 3/d a,d,c,b
0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
∞/nil 4/a 3/d 2/d
1/a
∞/nil ∞/nil 5/d 6/d 4/c 5/c 4/c 5/c
17
Dijkstra’s Algorithm: Example
a4c2e 3
111 1 4
bdf
25
Covered abcdef
−
0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
1/a
∞/nil 4/a 3/d 2/d
∞/nil ∞/nil 5/d 6/d 4/c 5/c 4/c 5/c
a
a,d
a,d,c 3/d
a,d,c,b
a,d,c,b,e 5/c
17
Dijkstra’s Algorithm: Example
a4c2e 3
111 1 4
bdf
25
Covered abcdef
−
0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
1/a
∞/nil 4/a 3/d 2/d
∞/nil ∞/nil 5/d 6/d 4/c 5/c 4/c 5/c
a
a,d
a,d,c 3/d
a,d,c,b
a,d,c,b,e 5/c a,d,c,b,e,f
17
Dijkstra’s Algorithm: Tracing Paths
The array prev is not really needed, unless we want to retrace the shortest paths from node a:
a c2e
3
bdf
2
1
1
18
Negative Weights
In our example, we used positive weights, and for a good reason: Dijkstra’s algorithm may not work otherwise!
In this example, the greedy pick—choosing 3 the edge from a to b—is clearly the wrong
b
a -2
4c
one.
19