COMP90038 Algorithms and Complexity
Greedy Algorithms: Prim and Dijkstra
Olya Ohrimenko
(Slides from Harald Søndergaard)
Lecture 20
Semester 2, 2021
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 1 / 22
Announcements
Assignment 2 is out on LMS.
Olya’s consultation session (Zoom link via LMS):
Tuesday October 12, 2:30 – 3:30 pm
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 2 / 22
Last two lectures: Dynamic Programming
We looked at dynamic programming for knapsack problem and two graph problems:
Warshall algorithm: Computing the transitive closure of a directed graph; and
Floyd’s algorithm: Finding shortest distances in weighted directed graphs.
Python code available for all algorithms on LMS.
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 3 / 22
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, and 1, and we want to change 35 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 35 cents. (In this case we use 25+10 cents.)
This greedy strategy will work for 35 cents but not always. For which of these it will not work? (a) 50 (b) 30 (c) 5.
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 4 / 22
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
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 5 / 22
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:
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 6 / 22
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
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 7 / 22
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
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 8 / 22
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
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 9 / 22
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 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 .
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 10 / 22
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 weight(u,w) < cost[w] then
cost[w] ← weight(u,w)
prev[w] ← u
Update(Q,w,cost[w]) ⊲ rearranges priority queue
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 11 / 22
Prim’s Algorithm: Example
a6c5e 541234 b2d4f
TreeT abcdef
− 0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 12 / 22
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
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne
12 / 22
Prim’s Algorithm: Example
a6c5e 541234 b2d4f
TreeT abcdef
−
a a,d
0/nil ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil
5/a 6/a 2/d 2/d
4/a ∞/nil ∞/nil ∞/nil 4/d
Algorithms and Complexity (Sem 2, 2021)
Prim and Dijkstra
© University of Melbourne
12 / 22
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 4/a 2/d 2/d
1/b
∞/nil ∞/nil ∞/nil 4/d ∞/nil 4/d
Algorithms and Complexity (Sem 2, 2021)
Prim and Dijkstra
© University of Melbourne
12 / 22
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 4/a 2/d 2/d
1/b
∞/nil ∞/nil ∞/nil 4/d ∞/nil 4/d
5/c 3/c
Algorithms and Complexity (Sem 2, 2021)
Prim and Dijkstra
© University of Melbourne
12 / 22
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
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 12 / 22
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
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 12 / 22
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 (again, 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 |).
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 13 / 22
Kruskal’s Algorithm (Not Examinable)
An alternative minimal-spanning-tree algorithm, also greedy, is Kruskal’s algorithm.
The algorithm is explained in Levitin’s Section 9.2, which we skip. For sparse graphs, if properly implemented, Kruskal’s algorithm will
generally do better than Prim’s.
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 14 / 22
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.
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 15 / 22
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 dist[u]+weight(u,w)