COSC1285/2123: Algorithms & Analysis – Greedy Techniques
COSC1285/2123: Algorithms & Analysis
Greedy Techniques
Hoang MIT University
Email : sonhoang. .au
Lecture 9
(RMIT University) Greedy Techniques Lecture 9 1 / 61
Overview
Levitin – The design and analysis of algorithms
This week we will be covering the material from Chapter 9.
Learning outcomes:
• Understand and be able to apply the greedy approach to solve
interesting problems.
• Examples:
• spanning tree – Prim’s algorithm
• spanning tree – Kruskal’s algorithm
• single source shortest-path – Dijkstra’s algorithm
• data compression
(RMIT University) Greedy Techniques Lecture 9 2 / 61
Outline
1 Overview
2 Prim’s Algorithm
3 Kruskal’s Algorithm
4 Dijkstra’s Algorithm
5 Data Compression
6 Summary
(RMIT University) Greedy Techniques Lecture 9 3 / 61
Overview
1 Overview
2 Prim’s Algorithm
3 Kruskal’s Algorithm
4 Dijkstra’s Algorithm
5 Data Compression
6 Summary
(RMIT University) Greedy Techniques Lecture 9 4 / 61
Greedy Algorithms
Greedy Algorithms build up a solution piece by piece, always choosing
the next piece that offers the most immediate and obvious benefit.
Sometimes such an approach can lead to an inferior solution, but in
other cases it can lead to a simple and optimal solution.
(RMIT University) Greedy Techniques Lecture 9 5 / 61
Overview
1 Overview
2 Prim’s Algorithm
3 Kruskal’s Algorithm
4 Dijkstra’s Algorithm
5 Data Compression
6 Summary
(RMIT University) Greedy Techniques Lecture 9 6 / 61
Minimum Spanning Tree
Spanning Tree Problem
A spanning tree of a connected graph is a connected acyclic subgraph
(i.e. tree) which contains all the vertices of the graph and a subset of
edges from the original graph.
Minimum Spanning Tree Problem
A minimum spanning tree of a weighted connected graph is the
spanning tree of the smallest total weight (sum of the weights on all of
the tree’s edges).
a b
c d
1
5 2
3
Graph
a b
c d
1
2
3
w(T1) = 6
a b
c d
1
5
3
w(T2) = 9
a b
c d
1
5 2
w(T3) = 8
(RMIT University) Greedy Techniques Lecture 9 7 / 61
Minimum Spanning Tree
Spanning Tree Problem
A spanning tree of a connected graph is a connected acyclic subgraph
(i.e. tree) which contains all the vertices of the graph and a subset of
edges from the original graph.
Minimum Spanning Tree Problem
A minimum spanning tree of a weighted connected graph is the
spanning tree of the smallest total weight (sum of the weights on all of
the tree’s edges).
a b
c d
1
5 2
3
Graph
a b
c d
1
2
3
w(T1) = 6
a b
c d
1
5
3
w(T2) = 9
a b
c d
1
5 2
w(T3) = 8
(RMIT University) Greedy Techniques Lecture 9 7 / 61
Minimum Spanning Tree
Spanning Tree Problem
A spanning tree of a connected graph is a connected acyclic subgraph
(i.e. tree) which contains all the vertices of the graph and a subset of
edges from the original graph.
Minimum Spanning Tree Problem
A minimum spanning tree of a weighted connected graph is the
spanning tree of the smallest total weight (sum of the weights on all of
the tree’s edges).
a b
c d
1
5 2
3
Graph
a b
c d
1
2
3
w(T1) = 6
a b
c d
1
5
3
w(T2) = 9
a b
c d
1
5 2
w(T3) = 8
(RMIT University) Greedy Techniques Lecture 9 7 / 61
Applications of Minimum Spanning Tree
• Designing networks (phones, computers etc): Want to connect up
a series of offices with telephone or wired lines, but want to
minimise cost.
• Approximate solutions to hard problems: travelling salesman
• Generation of perfect mazes
(RMIT University) Greedy Techniques Lecture 9 8 / 61
Prim’s Algorithm – Sketch
Prim’s Algorithm is one approach to find minimum spanning tree.
Idea: Select one vertex at a time and add to tree.
1 Start with one arbitrary selected vertex and add this to tree.
2 Then at each iteration add a neighbouring vertex to the tree that
has minimum edge weight to one of the vertices in the current
tree. It must not be in the tree.
3 When all vertices added to tree, we are done.
Note:
• Use a min priority queue to quickly find this neighbouring vertex
with minimum edge weight
• When adding, we may need to update the smallest edge weight to
a vertex in neighbour set as there may be a smallest edge weight
from updated tree to new neighbour set.
(RMIT University) Greedy Techniques Lecture 9 9 / 61
Prim’s Algorithm – Sketch
Prim’s Algorithm is one approach to find minimum spanning tree.
Idea: Select one vertex at a time and add to tree.
1 Start with one arbitrary selected vertex and add this to tree.
2 Then at each iteration add a neighbouring vertex to the tree that
has minimum edge weight to one of the vertices in the current
tree. It must not be in the tree.
3 When all vertices added to tree, we are done.
Note:
• Use a min priority queue to quickly find this neighbouring vertex
with minimum edge weight
• When adding, we may need to update the smallest edge weight to
a vertex in neighbour set as there may be a smallest edge weight
from updated tree to new neighbour set.
(RMIT University) Greedy Techniques Lecture 9 9 / 61
Prim’s Algorithm – Sketch
Prim’s Algorithm is one approach to find minimum spanning tree.
Idea: Select one vertex at a time and add to tree.
1 Start with one arbitrary selected vertex and add this to tree.
2 Then at each iteration add a neighbouring vertex to the tree that
has minimum edge weight to one of the vertices in the current
tree. It must not be in the tree.
3 When all vertices added to tree, we are done.
Note:
• Use a min priority queue to quickly find this neighbouring vertex
with minimum edge weight
• When adding, we may need to update the smallest edge weight to
a vertex in neighbour set as there may be a smallest edge weight
from updated tree to new neighbour set.
(RMIT University) Greedy Techniques Lecture 9 9 / 61
Prim’s Algorithm – Sketch
Prim’s Algorithm is one approach to find minimum spanning tree.
Idea: Select one vertex at a time and add to tree.
1 Start with one arbitrary selected vertex and add this to tree.
2 Then at each iteration add a neighbouring vertex to the tree that
has minimum edge weight to one of the vertices in the current
tree. It must not be in the tree.
3 When all vertices added to tree, we are done.
Note:
• Use a min priority queue to quickly find this neighbouring vertex
with minimum edge weight
• When adding, we may need to update the smallest edge weight to
a vertex in neighbour set as there may be a smallest edge weight
from updated tree to new neighbour set.
(RMIT University) Greedy Techniques Lecture 9 9 / 61
Prim’s Algorithm – Sketch
Prim’s Algorithm is one approach to find minimum spanning tree.
Idea: Select one vertex at a time and add to tree.
1 Start with one arbitrary selected vertex and add this to tree.
2 Then at each iteration add a neighbouring vertex to the tree that
has minimum edge weight to one of the vertices in the current
tree. It must not be in the tree.
3 When all vertices added to tree, we are done.
Note:
• Use a min priority queue to quickly find this neighbouring vertex
with minimum edge weight
• When adding, we may need to update the smallest edge weight to
a vertex in neighbour set as there may be a smallest edge weight
from updated tree to new neighbour set.
(RMIT University) Greedy Techniques Lecture 9 9 / 61
Prim’s Algorithm – Sketch
Prim’s Algorithm is one approach to find minimum spanning tree.
Idea: Select one vertex at a time and add to tree.
1 Start with one arbitrary selected vertex and add this to tree.
2 Then at each iteration add a neighbouring vertex to the tree that
has minimum edge weight to one of the vertices in the current
tree. It must not be in the tree.
3 When all vertices added to tree, we are done.
Note:
• Use a min priority queue to quickly find this neighbouring vertex
with minimum edge weight
• When adding, we may need to update the smallest edge weight to
a vertex in neighbour set as there may be a smallest edge weight
from updated tree to new neighbour set.
(RMIT University) Greedy Techniques Lecture 9 9 / 61
Prim’s Algorithm – Pseudocode
ALGORITHM Prim (G)
/* Prim’s algorithm for constructing a minimum spanning tree. */
/* INPUT : A weighted connected graph G = 〈V ,E〉 */
/* OUTPUT : The set of edges ET composing a minimum spanning tree.
*/
1: VT = {v0} . Initialized with arbitrary vertex v0.
2: ET = ∅
3: for i = 1 to |V | − 1 do
4: find a minimum-weight edge e∗ = (v∗,u∗) among all
5: the edges (v ,u) such that v is in VT and u is in V − VT .
6: VT = VT ∪ {u∗}
7: ET = ET ∪ {e∗}
8: end for
9: return ET
(RMIT University) Greedy Techniques Lecture 9 10 / 61
Prim’s Algorithm – Example
a
b c
d e
f g
7
8
5
9
7
5
15
6
8
9
11
VT = {}, PQ = {}
(RMIT University) Greedy Techniques Lecture 9 11 / 61
Prim’s Algorithm – Example
a
b c
d e
f g
7
8
5
9
7
5
15
6
8
9
11
d
VT = {d}, PQ = {(a,5), (f ,6), (b,9), (e,15)}
(RMIT University) Greedy Techniques Lecture 9 12 / 61
Prim’s Algorithm – Example
a
b c
d e
f g
7
8
5
9
7
5
15
6
8
9
11
d
a
VT = {d ,a}, PQ = {(f ,6), (b,7),��
�(b,9), (e,15)}
(RMIT University) Greedy Techniques Lecture 9 12 / 61
Prim’s Algorithm – Example
a
b c
d e
f g
7
8
5
9
7
5
15
6
8
9
11
d
a
f
VT = {d ,a, f}, PQ = {(b,7), (e,8), (g,11),����(e,15)}
(RMIT University) Greedy Techniques Lecture 9 12 / 61
Prim’s Algorithm – Example
a
b c
d e
f g
7
8
5
9
7
5
15
6
8
9
11
d
a
f
b
VT = {d ,a, f ,b}, PQ = {(e,7),��
�(e,8), (c,8), (g,11)}
(RMIT University) Greedy Techniques Lecture 9 12 / 61
Prim’s Algorithm – Example
a
b c
d e
f g
7
8
5
9
7
5
15
6
8
9
11
d
a
f
b
e
VT = {d ,a, f ,b,e}, PQ = {(c,5),��
�(c,8), (g,9),����(g,11)}
(RMIT University) Greedy Techniques Lecture 9 12 / 61
Prim’s Algorithm – Example
a
b c
d e
f g
7
8
5
9
7
5
15
6
8
9
11
d
a
f
b
e
c
VT = {d ,a, f ,b,e, c}, PQ = {(g,9)}
(RMIT University) Greedy Techniques Lecture 9 12 / 61
Prim’s Algorithm – Example
a
b c
d e
f g
7
8
5
9
7
5
15
6
8
9
11
d
a
f
b
e
c
g
VT = {d ,a, f ,b,e, c,g}, PQ = {}
(RMIT University) Greedy Techniques Lecture 9 12 / 61
Minecraft Maze Generation
(RMIT University) Greedy Techniques Lecture 9 13 / 61
Prim’s Algorithm – Summary
• The algorithm always gives the optimal solution, regardless of
where you start. See Levitin Chp 9.1 for the proof.
• The efficiency of the algorithm using a min-heap and an
adjacency list is O(|E | log |V |).
(RMIT University) Greedy Techniques Lecture 9 14 / 61
Prim’s Algorithm – Summary
• The algorithm always gives the optimal solution, regardless of
where you start. See Levitin Chp 9.1 for the proof.
• The efficiency of the algorithm using a min-heap and an
adjacency list is O(|E | log |V |).
(RMIT University) Greedy Techniques Lecture 9 14 / 61
Overview
1 Overview
2 Prim’s Algorithm
3 Kruskal’s Algorithm
4 Dijkstra’s Algorithm
5 Data Compression
6 Summary
(RMIT University) Greedy Techniques Lecture 9 15 / 61
Kruskal’s Algorithm – Sketch
Kruskal’s algorithm is an alternative method to find minimum spanning
trees. (We will explore why have two algorithms at end of this section)
Idea: Select one edge at a time and add to tree.
1 Start with empty tree.
2 Add one edge at a time to the current tree. Edge selected is the
one with minimum weight and doesn’t create a cycle.
3 Terminate when |V | − 1 such edges have been added. (A tree of
|V | nodes has |V | − 1 edges).
Note:
• To be fast in edge selection, we initially sort all edges from
smallest to largest by weight.
• Note that the nodes are not always connected in the intermediate
stages of the algorithm.
(RMIT University) Greedy Techniques Lecture 9 16 / 61
Kruskal’s Algorithm – Sketch
Kruskal’s algorithm is an alternative method to find minimum spanning
trees. (We will explore why have two algorithms at end of this section)
Idea: Select one edge at a time and add to tree.
1 Start with empty tree.
2 Add one edge at a time to the current tree. Edge selected is the
one with minimum weight and doesn’t create a cycle.
3 Terminate when |V | − 1 such edges have been added. (A tree of
|V | nodes has |V | − 1 edges).
Note:
• To be fast in edge selection, we initially sort all edges from
smallest to largest by weight.
• Note that the nodes are not always connected in the intermediate
stages of the algorithm.
(RMIT University) Greedy Techniques Lecture 9 16 / 61
Kruskal’s Algorithm – Sketch
Kruskal’s algorithm is an alternative method to find minimum spanning
trees. (We will explore why have two algorithms at end of this section)
Idea: Select one edge at a time and add to tree.
1 Start with empty tree.
2 Add one edge at a time to the current tree. Edge selected is the
one with minimum weight and doesn’t create a cycle.
3 Terminate when |V | − 1 such edges have been added. (A tree of
|V | nodes has |V | − 1 edges).
Note:
• To be fast in edge selection, we initially sort all edges from
smallest to largest by weight.
• Note that the nodes are not always connected in the intermediate
stages of the algorithm.
(RMIT University) Greedy Techniques Lecture 9 16 / 61
Kruskal’s Algorithm – Sketch
Kruskal’s algorithm is an alternative method to find minimum spanning
trees. (We will explore why have two algorithms at end of this section)
Idea: Select one edge at a time and add to tree.
1 Start with empty tree.
2 Add one edge at a time to the current tree. Edge selected is the
one with minimum weight and doesn’t create a cycle.
3 Terminate when |V | − 1 such edges have been added. (A tree of
|V | nodes has |V | − 1 edges).
Note:
• To be fast in edge selection, we initially sort all edges from
smallest to largest by weight.
• Note that the nodes are not always connected in the intermediate
stages of the algorithm.
(RMIT University) Greedy Techniques Lecture 9 16 / 61
Kruskal’s Algorithm – Sketch
Kruskal’s algorithm is an alternative method to find minimum spanning
trees. (We will explore why have two algorithms at end of this section)
Idea: Select one edge at a time and add to tree.
1 Start with empty tree.
2 Add one edge at a time to the current tree. Edge selected is the
one with minimum weight and doesn’t create a cycle.
3 Terminate when |V | − 1 such edges have been added. (A tree of
|V | nodes has |V | − 1 edges).
Note:
• To be fast in edge selection, we initially sort all edges from
smallest to largest by weight.
• Note that the nodes are not always connected in the intermediate
stages of the algorithm.
(RMIT University) Greedy Techniques Lecture 9 16 / 61
Kruskal’s Algorithm – Example
a
b
f
c
d
e
3
5
6
1
4 4 6
5
82
All Edges : bc ef ab bf cf af df ae cd de
1 2 3 4 4 5 5 6 6 8
Tree Edges : ∅
∅
(RMIT University) Greedy Techniques Lecture 9 17 / 61
Kruskal’s Algorithm – Example
a
b
f
c
d
e
3
5
6
1
4 4 6
5
82
All Edges : bc ef ab bf cf af df ae cd de
1 2 3 4 4 5 5 6 6 8
Tree Edges : ∅
∅
(RMIT University) Greedy Techniques Lecture 9 18 / 61
Kruskal’s Algorithm – Example
a
b
f
c
d
e
3
5
6
1
4 4 6
5
82
All Edges : bc ef ab bf cf af df ae cd de
1 2 3 4 4 5 5 6 6 8
Tree Edges : bc
1
(RMIT University) Greedy Techniques Lecture 9 19 / 61
Kruskal’s Algorithm – Example
a
b
f
c
d
e
3
5
6
1
4 4 6
5
82
All Edges : bc ef ab bf cf af df ae cd de
1 2 3 4 4 5 5 6 6 8
Tree Edges : bc ef
1 2
(RMIT University) Greedy Techniques Lecture 9 20 / 61
Kruskal’s Algorithm – Example
a
b
f
c
d
e
3
5
6
1
4 4 6
5
82
All Edges : bc ef ab bf cf af df ae cd de
1 2 3 4 4 5 5 6 6 8
Tree Edges : bc ef ab
1 2 3
(RMIT University) Greedy Techniques Lecture 9 21 / 61
Kruskal’s Algorithm – Example
a
b
f
c
d
e
3
5
6
1
4 4 6
5
82
All Edges : bc ef ab bf cf af df ae cd de
1 2 3 4 4 5 5 6 6 8
Tree Edges : bc ef ab bf
1 2 3 4
(RMIT University) Greedy Techniques Lecture 9 22 / 61
Kruskal’s Algorithm – Example
a
b
f
c
d
e
3
5
6
1
4 4 6
5
82
All Edges : bc ef ab bf cf af df ae cd de
1 2 3 4 4 5 5 6 6 8
Tree Edges : bc ef ab bf df
1 2 3 4 5
(RMIT University) Greedy Techniques Lecture 9 23 / 61
Kruskal’s Algorithm – Summary
• Conceptually, Kruskal’s algorithm appears easier than Prim’s
algorithm, but it is not.
• It is harder to implement because checking for cycles requires us
to maintain a forest of trees on the intermediate steps.
• This is essentially a case of Union-Find algorithm.
• With an efficient Union-find algorithm, Kruskal’s algorithm is
slightly less efficient that Prim’s algorithm, requiring O(|E | log |E |)
time (dominated by the time to sort the edges).
• When the graph is sparse, |E | same order of magnitude as |V |,
then Kruskal’s algorithm can usually be faster than Prim’s
(although same asymptotic complexity)
(RMIT University) Greedy Techniques Lecture 9 24 / 61
Kruskal’s Algorithm – Summary
• Conceptually, Kruskal’s algorithm appears easier than Prim’s
algorithm, but it is not.
• It is harder to implement because checking for cycles requires us
to maintain a forest of trees on the intermediate steps.
• This is essentially a case of Union-Find algorithm.
• With an efficient Union-find algorithm, Kruskal’s algorithm is
slightly less efficient that Prim’s algorithm, requiring O(|E | log |E |)
time (dominated by the time to sort the edges).
• When the graph is sparse, |E | same order of magnitude as |V |,
then Kruskal’s algorithm can usually be faster than Prim’s
(although same asymptotic complexity)
(RMIT University) Greedy Techniques Lecture 9 24 / 61
Kruskal’s Algorithm – Summary
• Conceptually, Kruskal’s algorithm appears easier than Prim’s
algorithm, but it is not.
• It is harder to implement because checking for cycles requires us
to maintain a forest of trees on the intermediate steps.
• This is essentially a case of Union-Find algorithm.
• With an efficient Union-find algorithm, Kruskal’s algorithm is
slightly less efficient that Prim’s algorithm, requiring O(|E | log |E |)
time (dominated by the time to sort the edges).
• When the graph is sparse, |E | same order of magnitude as |V |,
then Kruskal’s algorithm can usually be faster than Prim’s
(although same asymptotic complexity)
(RMIT University) Greedy Techniques Lecture 9 24 / 61
Kruskal’s Algorithm – Summary
• Conceptually, Kruskal’s algorithm appears easier than Prim’s
algorithm, but it is not.
• It is harder to implement because checking for cycles requires us
to maintain a forest of trees on the intermediate steps.
• This is essentially a case of Union-Find algorithm.
• With an efficient Union-find algorithm, Kruskal’s algorithm is
slightly less efficient that Prim’s algorithm, requiring O(|E | log |E |)
time (dominated by the time to sort the edges).
• When the graph is sparse, |E | same order of magnitude as |V |,
then Kruskal’s algorithm can usually be faster than Prim’s
(although same asymptotic complexity)
(RMIT University) Greedy Techniques Lecture 9 24 / 61
Kruskal’s Algorithm – Summary
• Conceptually, Kruskal’s algorithm appears easier than Prim’s
algorithm, but it is not.
• It is harder to implement because checking for cycles requires us
to maintain a forest of trees on the intermediate steps.
• This is essentially a case of Union-Find algorithm.
• With an efficient Union-find algorithm, Kruskal’s algorithm is
slightly less efficient that Prim’s algorithm, requiring O(|E | log |E |)
time (dominated by the time to sort the edges).
• When the graph is sparse, |E | same order of magnitude as |V |,
then Kruskal’s algorithm can usually be faster than Prim’s
(although same asymptotic complexity)
(RMIT University) Greedy Techniques Lecture 9 24 / 61
Shortest Spanning Tree or Minimum Spanning Tree?
(RMIT University) Greedy Techniques Lecture 9 25 / 61
Overview
1 Overview
2 Prim’s Algorithm
3 Kruskal’s Algorithm
4 Dijkstra’s Algorithm
5 Data Compression
6 Summary
(RMIT University) Greedy Techniques Lecture 9 26 / 61
Shortest Paths in Graphs
Problem
Given a weighted connected graph, the shortest-path problem asks to
find the shortest path from a starting source vertex to a destination
target vertex.
(RMIT University) Greedy Techniques Lecture 9 27 / 61
Shortest Paths in Graphs
Problem
Given a weighted connected graph, the shortest-path problem asks to
find the shortest path from a starting source vertex to a destination
target vertex.
(RMIT University) Greedy Techniques Lecture 9 27 / 61
Dijkstra’s Algorithm
Problem
Given a weighted connected graph, the single-source shortest-paths
problem asks to find the shortest path to all vertices given a single
starting source vertex.
Idea:
• At all times, we maintain our best estimate of the shortest-path
distances from source vertex to all other vertices.
• Initially we do not know, so all these distance estimates are∞.
• But as the algorithm explores the graph, we update our estimates,
which converges to the true shortest path distance.
(RMIT University) Greedy Techniques Lecture 9 28 / 61
Dijkstra’s Algorithm
Problem
Given a weighted connected graph, the single-source shortest-paths
problem asks to find the shortest path to all vertices given a single
starting source vertex.
Idea:
• At all times, we maintain our best estimate of the shortest-path
distances from source vertex to all other vertices.
• Initially we do not know, so all these distance estimates are∞.
• But as the algorithm explores the graph, we update our estimates,
which converges to the true shortest path distance.
(RMIT University) Greedy Techniques Lecture 9 28 / 61
Dijkstra’s Algorithm
Problem
Given a weighted connected graph, the single-source shortest-paths
problem asks to find the shortest path to all vertices given a single
starting source vertex.
Idea:
• At all times, we maintain our best estimate of the shortest-path
distances from source vertex to all other vertices.
• Initially we do not know, so all these distance estimates are∞.
• But as the algorithm explores the graph, we update our estimates,
which converges to the true shortest path distance.
(RMIT University) Greedy Techniques Lecture 9 28 / 61
Dijkstra’s Algorithm – Sketch
Maintain a set S of vertices whose final shortest-path weights from the
source s have already been determined.
1 Initially S is empty. Initialise distance estmates to∞ for all
non-source vertices. Distance of source vertex is 0.
2 Select the vertex v not in S with the minimum shortest-path
estimate.
3 Add v to S.
4 Update our distance estimates to neighbouring vertices that are
not in S.
5 Repeat from step 2, until all vertices have been added to S.
(RMIT University) Greedy Techniques Lecture 9 29 / 61
Dijkstra’s Algorithm – Sketch
Maintain a set S of vertices whose final shortest-path weights from the
source s have already been determined.
1 Initially S is empty. Initialise distance estmates to∞ for all
non-source vertices. Distance of source vertex is 0.
2 Select the vertex v not in S with the minimum shortest-path
estimate.
3 Add v to S.
4 Update our distance estimates to neighbouring vertices that are
not in S.
5 Repeat from step 2, until all vertices have been added to S.
(RMIT University) Greedy Techniques Lecture 9 29 / 61
Dijkstra’s Algorithm – Sketch
Maintain a set S of vertices whose final shortest-path weights from the
source s have already been determined.
1 Initially S is empty. Initialise distance estmates to∞ for all
non-source vertices. Distance of source vertex is 0.
2 Select the vertex v not in S with the minimum shortest-path
estimate.
3 Add v to S.
4 Update our distance estimates to neighbouring vertices that are
not in S.
5 Repeat from step 2, until all vertices have been added to S.
(RMIT University) Greedy Techniques Lecture 9 29 / 61
Dijkstra’s Algorithm – Sketch
Maintain a set S of vertices whose final shortest-path weights from the
source s have already been determined.
1 Initially S is empty. Initialise distance estmates to∞ for all
non-source vertices. Distance of source vertex is 0.
2 Select the vertex v not in S with the minimum shortest-path
estimate.
3 Add v to S.
4 Update our distance estimates to neighbouring vertices that are
not in S.
5 Repeat from step 2, until all vertices have been added to S.
(RMIT University) Greedy Techniques Lecture 9 29 / 61
Dijkstra’s Algorithm – Sketch
Maintain a set S of vertices whose final shortest-path weights from the
source s have already been determined.
1 Initially S is empty. Initialise distance estmates to∞ for all
non-source vertices. Distance of source vertex is 0.
2 Select the vertex v not in S with the minimum shortest-path
estimate.
3 Add v to S.
4 Update our distance estimates to neighbouring vertices that are
not in S.
5 Repeat from step 2, until all vertices have been added to S.
(RMIT University) Greedy Techniques Lecture 9 29 / 61
Dijkstra’s Algorithm – Sketch
Maintain a set S of vertices whose final shortest-path weights from the
source s have already been determined.
1 Initially S is empty. Initialise distance estmates to∞ for all
non-source vertices. Distance of source vertex is 0.
2 Select the vertex v not in S with the minimum shortest-path
estimate.
3 Add v to S.
4 Update our distance estimates to neighbouring vertices that are
not in S.
5 Repeat from step 2, until all vertices have been added to S.
(RMIT University) Greedy Techniques Lecture 9 29 / 61
Dijkstra’s Algorithm – Pseudocode
ALGORITHM Dijkstra (G, s)
/* Dijkstra’s algorithm for single-source shortest paths. */
/* INPUT : A weighted connected graph G = 〈V ,E〉 and a starting vertex s. */
/* OUTPUT : The length dv of a shortest path from s to v and its penultimate vertex pv for every
vertex v in V . */
1: INITIALIZE(Q) . Initialize vertex priority queue.
2: for each v in V do
3: dv =∞; pv = ∅
4: INSERT (Q, v , dv ) . Initialize vertex priority in the queue.
5: end for
6: ds = 0;VT = ∅
7: UPDATE(Q, s, ds) . Update the priority of s with ds .
8: for i = 0 to |V | − 1 do
9: u∗ = DELETEMIN(Q) . Delete the minimum priority element.
10: VT = VT ∪ {u∗}
11: for each u in V − VT adjacent to u∗ do
12: if du∗ + w(u∗, u) < du then
13: du = du∗ + w(u∗, u); pu = u∗
14: UPDATE(Q, u, du)
15: end if
16: end for
17: end for
(RMIT University) Greedy Techniques Lecture 9 30 / 61
Dijkstra’s Algorithm – Example
a
b
d
c
e
3
7
4
2 5 6
4
a(a,0) b(-,∞) c(-,∞) d(-,∞) e(-,∞)
S = { }
(RMIT University) Greedy Techniques Lecture 9 31 / 61
Dijkstra’s Algorithm – Example
a
b
d
c
e
3
7
4
2 5 6
4
b(a,3) c(-,∞) d(a,7) e(-,∞)
S = {a(a,0)}
(RMIT University) Greedy Techniques Lecture 9 32 / 61
Dijkstra’s Algorithm – Example
a
b
d
c
e
3
7
4
2 5 6
4
b(a,3) c(-,∞) d(a,7) e(-,∞)
S = {a(a,0)}
(RMIT University) Greedy Techniques Lecture 9 33 / 61
Dijkstra’s Algorithm – Example
a
b
d
c
e
3
7
4
2 5 6
4
c(b,3 + 4) d(b,3 + 2) e(-,∞)
S = {a(a,0), b(a,3)}
(RMIT University) Greedy Techniques Lecture 9 34 / 61
Dijkstra’s Algorithm – Example
a
b
d
c
e
3
7
4
2 5 6
4
c(b,7) d(b,5) e(-,∞)
S = {a(a,0), b(a,3)}
(RMIT University) Greedy Techniques Lecture 9 35 / 61
Dijkstra’s Algorithm – Example
a
b
d
c
e
3
7
4
2 5 6
4
c(b,7) e(d,5+4)
S = {a(a,0), b(a,3), d(b,5)}
(RMIT University) Greedy Techniques Lecture 9 36 / 61
Dijkstra’s Algorithm – Example
a
b
d
c
e
3
7
4
2 5 6
4
e(d,9)
S = {a(a,0), b(a,3), d(b,5), c(b,7)}
(RMIT University) Greedy Techniques Lecture 9 37 / 61
Dijkstra’s Algorithm – Example
a
b
d
c
e
3
7
4
2 5 6
4
S = {a(a,0), b(a,3), d(b,5), c(b,7), e(d,9)}
(RMIT University) Greedy Techniques Lecture 9 38 / 61
Dijkstra’s Algorithm – Example
So, we have the following distances from vertex a:
a(a,0) b(a,3) d(b,5) c(b,7) e(d,9)
Which gives the following shortest paths:
Length Path
3 a - b
5 a - b - d
7 a - b - c
9 a - b - d - e
(RMIT University) Greedy Techniques Lecture 9 39 / 61
Dijkstra’s Algorithm – Example
So, we have the following distances from vertex a:
a(a,0) b(a,3) d(b,5) c(b,7) e(d,9)
Which gives the following shortest paths:
Length Path
3 a - b
5 a - b - d
7 a - b - c
9 a - b - d - e
(RMIT University) Greedy Techniques Lecture 9 39 / 61
Dijkstra’s Algorithm – Summary
• Dijkstra’s algorithm is guaranteed to always return the optimal
solution. This is not necessarily true for all greedy algorithms.
• If we use an adjacency list and a min-heap, the algorithm runs in
Θ(|E | log |V |) time.
(RMIT University) Greedy Techniques Lecture 9 40 / 61
Dijkstra’s Algorithm – Summary
• Dijkstra’s algorithm is guaranteed to always return the optimal
solution. This is not necessarily true for all greedy algorithms.
• If we use an adjacency list and a min-heap, the algorithm runs in
Θ(|E | log |V |) time.
(RMIT University) Greedy Techniques Lecture 9 40 / 61
Overview
1 Overview
2 Prim’s Algorithm
3 Kruskal’s Algorithm
4 Dijkstra’s Algorithm
5 Data Compression
6 Summary
(RMIT University) Greedy Techniques Lecture 9 41 / 61
What is data compression?
• Data compression is the process of representing a data source in
a reduced form. If there is no loss of information, it is called
lossless compression.
(RMIT University) Greedy Techniques Lecture 9 42 / 61
Fixed Length Codes
The simplest encoding/decoding approach is to create a mapping from
source alphabet to strings (codewords), where these codewords are
fixed in length.
Example (Fixed Length Coding)
Given S = {a, c,g, t}, Σ = {0,1}, and the encoding scheme,
a 7→ 00,
c 7→ 01,
g 7→ 10,
t 7→ 11,
then φ(gattaca) = 10001111000100.
(RMIT University) Greedy Techniques Lecture 9 43 / 61
Fixed Length Codes
The simplest encoding/decoding approach is to create a mapping from
source alphabet to strings (codewords), where these codewords are
fixed in length.
Example (Fixed Length Coding)
Given S = {a, c,g, t}, Σ = {0,1}, and the encoding scheme,
a 7→ 00,
c 7→ 01,
g 7→ 10,
t 7→ 11,
then φ(gattaca) = 10001111000100.
(RMIT University) Greedy Techniques Lecture 9 43 / 61
Fixed Length Codes – ASCII
ASCII
American Standard Code for Information Interchange is a fixed length
character encoding scheme over an alphabet of 128 characters.
char* string = �AARDVARK�
A A R D V A R K
0x41 0x41 0x52 0x44 0x56 0x41 0x52 0x4B
1000001 1000001 1010010 1000100 1010110 1000001 1010010 1001011
(RMIT University) Greedy Techniques Lecture 9 44 / 61
Variable Length Codes
• Fixed length codewords are not the optimal in average bits per
source symbol.
• Why? The frequency of appearance of each member of the
source alphabet may not be uniformly distributed.
• Consider the letters ‘e’ and ‘z’ in natural language text, and using
the same length codewords to represent both.
• e.g., “zee”
• Using ascii where each letter represented by 7 bits, this is 3 * 7 =
21 bits
(RMIT University) Greedy Techniques Lecture 9 45 / 61
Variable Length Codes
• Fixed length codewords are not the optimal in average bits per
source symbol.
• Why? The frequency of appearance of each member of the
source alphabet may not be uniformly distributed.
• Consider the letters ‘e’ and ‘z’ in natural language text, and using
the same length codewords to represent both.
• e.g., “zee”
• Using ascii where each letter represented by 7 bits, this is 3 * 7 =
21 bits
(RMIT University) Greedy Techniques Lecture 9 45 / 61
Character Frequency
Character Frequency Probability
e 24,600,752 0.0880
t 18,443,242 0.0660
a 17,379,446 0.0621
...
...
...
j 671,765 0.0024
q 264,712 0.0009
z 186,802 0.0007
The frequency of appearance of characters from the English alphabet extracted from
a 267 MB segment of SGML-tagged newspaper text drawn from the WSJ component
of the TREC data set.
(RMIT University) Greedy Techniques Lecture 9 46 / 61
Variable Length Codes
Solution?
• A variable length code maps each member of a source alphabet to
a codeword string, but the length of codewords is no longer fixed.
• E.g., use a shorter codeword for ’e’ and a larger one for ’z’.
• “zee” (hypothetically use 2 bit code for ’e’ and ’10’ bit code for z,
this is 10 + 2*2 = 14 bits)
• However, not all possible variable length coding schemes are
decodeable.
(RMIT University) Greedy Techniques Lecture 9 47 / 61
Variable Length Codes
Solution?
• A variable length code maps each member of a source alphabet to
a codeword string, but the length of codewords is no longer fixed.
• E.g., use a shorter codeword for ’e’ and a larger one for ’z’.
• “zee” (hypothetically use 2 bit code for ’e’ and ’10’ bit code for z,
this is 10 + 2*2 = 14 bits)
• However, not all possible variable length coding schemes are
decodeable.
(RMIT University) Greedy Techniques Lecture 9 47 / 61
Variable Length Codes
Solution?
• A variable length code maps each member of a source alphabet to
a codeword string, but the length of codewords is no longer fixed.
• E.g., use a shorter codeword for ’e’ and a larger one for ’z’.
• “zee” (hypothetically use 2 bit code for ’e’ and ’10’ bit code for z,
this is 10 + 2*2 = 14 bits)
• However, not all possible variable length coding schemes are
decodeable.
(RMIT University) Greedy Techniques Lecture 9 47 / 61
Variable Length Codes – Decoding
Symbol a b c d e f g
Frequency 25 12 9 4 3 2 1
Symbol Codeword `i
a 0 1
b 1 1
c 00 2
d 01 2
e 10 2
f 11 3
g 110 3
Decode: 0010100010000111001011
Variable length codes must be chosen so text is uniquly decodeable.
(RMIT University) Greedy Techniques Lecture 9 48 / 61
Variable Length Codes – Decoding
Symbol a b c d e f g
Frequency 25 12 9 4 3 2 1
Symbol Codeword `i
a 0 1
b 1 1
c 00 2
d 01 2
e 10 2
f 11 3
g 110 3
Decode: 0010100010000111001011
Variable length codes must be chosen so text is uniquly decodeable.
(RMIT University) Greedy Techniques Lecture 9 48 / 61
Variable Length Codes – Prefix codes
Prefix Codes: Variable length codewords where no codeword is a
prefix of any other codeword. Prefix codes are uniquely decodeable.
Symbol Codeword `i
a 0 1
b 100 3
c 110 3
d 111 3
e 1010 4
(RMIT University) Greedy Techniques Lecture 9 49 / 61
Huffman’s Code – Sketch
Huffman Algorithm generates prefix codes that are optimal in the
average number of bits per symbol.
Idea: Build prefix tree bottom up. Read the codes from this prefix tree.
1 For each symbol, calculate the probability of appearance.
Construct a leaf node for it.
2 Put these leaf nodes to the set of candidate nodes (to merge).
3 Select the two nodes with the lowest probability (from candidate
nodes) and combine them in a “bottom-up” tree construction.
4 The new parent has a probability equal to the sum of the two child
probabilities, and replaces the two children in the set of candidate
nodes. Add links to the children, one link with labelled ’0’, the
other ’1’.
5 When only one candidate node remains, a tree has been formed,
and codewords can be read from the edge labels of a tree.
(RMIT University) Greedy Techniques Lecture 9 50 / 61
Huffman’s Code – Sketch
Huffman Algorithm generates prefix codes that are optimal in the
average number of bits per symbol.
Idea: Build prefix tree bottom up. Read the codes from this prefix tree.
1 For each symbol, calculate the probability of appearance.
Construct a leaf node for it.
2 Put these leaf nodes to the set of candidate nodes (to merge).
3 Select the two nodes with the lowest probability (from candidate
nodes) and combine them in a “bottom-up” tree construction.
4 The new parent has a probability equal to the sum of the two child
probabilities, and replaces the two children in the set of candidate
nodes. Add links to the children, one link with labelled ’0’, the
other ’1’.
5 When only one candidate node remains, a tree has been formed,
and codewords can be read from the edge labels of a tree.
(RMIT University) Greedy Techniques Lecture 9 50 / 61
Huffman’s Code – Sketch
Huffman Algorithm generates prefix codes that are optimal in the
average number of bits per symbol.
Idea: Build prefix tree bottom up. Read the codes from this prefix tree.
1 For each symbol, calculate the probability of appearance.
Construct a leaf node for it.
2 Put these leaf nodes to the set of candidate nodes (to merge).
3 Select the two nodes with the lowest probability (from candidate
nodes) and combine them in a “bottom-up” tree construction.
4 The new parent has a probability equal to the sum of the two child
probabilities, and replaces the two children in the set of candidate
nodes. Add links to the children, one link with labelled ’0’, the
other ’1’.
5 When only one candidate node remains, a tree has been formed,
and codewords can be read from the edge labels of a tree.
(RMIT University) Greedy Techniques Lecture 9 50 / 61
Huffman’s Code – Sketch
Huffman Algorithm generates prefix codes that are optimal in the
average number of bits per symbol.
Idea: Build prefix tree bottom up. Read the codes from this prefix tree.
1 For each symbol, calculate the probability of appearance.
Construct a leaf node for it.
2 Put these leaf nodes to the set of candidate nodes (to merge).
3 Select the two nodes with the lowest probability (from candidate
nodes) and combine them in a “bottom-up” tree construction.
4 The new parent has a probability equal to the sum of the two child
probabilities, and replaces the two children in the set of candidate
nodes. Add links to the children, one link with labelled ’0’, the
other ’1’.
5 When only one candidate node remains, a tree has been formed,
and codewords can be read from the edge labels of a tree.
(RMIT University) Greedy Techniques Lecture 9 50 / 61
Huffman’s Code – Sketch
Huffman Algorithm generates prefix codes that are optimal in the
average number of bits per symbol.
Idea: Build prefix tree bottom up. Read the codes from this prefix tree.
1 For each symbol, calculate the probability of appearance.
Construct a leaf node for it.
2 Put these leaf nodes to the set of candidate nodes (to merge).
3 Select the two nodes with the lowest probability (from candidate
nodes) and combine them in a “bottom-up” tree construction.
4 The new parent has a probability equal to the sum of the two child
probabilities, and replaces the two children in the set of candidate
nodes. Add links to the children, one link with labelled ’0’, the
other ’1’.
5 When only one candidate node remains, a tree has been formed,
and codewords can be read from the edge labels of a tree.
(RMIT University) Greedy Techniques Lecture 9 50 / 61
Huffman’s Code – Sketch
Huffman Algorithm generates prefix codes that are optimal in the
average number of bits per symbol.
Idea: Build prefix tree bottom up. Read the codes from this prefix tree.
1 For each symbol, calculate the probability of appearance.
Construct a leaf node for it.
2 Put these leaf nodes to the set of candidate nodes (to merge).
3 Select the two nodes with the lowest probability (from candidate
nodes) and combine them in a “bottom-up” tree construction.
4 The new parent has a probability equal to the sum of the two child
probabilities, and replaces the two children in the set of candidate
nodes. Add links to the children, one link with labelled ’0’, the
other ’1’.
5 When only one candidate node remains, a tree has been formed,
and codewords can be read from the edge labels of a tree.
(RMIT University) Greedy Techniques Lecture 9 50 / 61
Huffman’s Code – Sketch
Huffman Algorithm generates prefix codes that are optimal in the
average number of bits per symbol.
Idea: Build prefix tree bottom up. Read the codes from this prefix tree.
1 For each symbol, calculate the probability of appearance.
Construct a leaf node for it.
2 Put these leaf nodes to the set of candidate nodes (to merge).
3 Select the two nodes with the lowest probability (from candidate
nodes) and combine them in a “bottom-up” tree construction.
4 The new parent has a probability equal to the sum of the two child
probabilities, and replaces the two children in the set of candidate
nodes. Add links to the children, one link with labelled ’0’, the
other ’1’.
5 When only one candidate node remains, a tree has been formed,
and codewords can be read from the edge labels of a tree.
(RMIT University) Greedy Techniques Lecture 9 50 / 61
– Example
0.05 0.05 0.10 0.20 0.30 0.20 0.10
a b c d e f g
Construct a from the Alphabet
{(a,0.05), (b,0.05), (c,0.1), (d ,0.2), (e,0.3), (f ,0.2), (g,0.1)}.
(RMIT University) Greedy Techniques Lecture 9 51 / 61
– Example
0.10
0.05
0
0.05
1
0.10 0.20 0.30 0.20 0.10
a b
c d e f g
Construct a from the Alphabet
{(a,0.05), (b,0.05), (c,0.1), (d ,0.2), (e,0.3), (f ,0.2), (g,0.1)}.
(RMIT University) Greedy Techniques Lecture 9 52 / 61
– Example
0.20
0.10
0.05
0
0.05
1
0
0.10
1
0.20 0.30 0.20 0.10
a b
c
d e f g
Construct a from the Alphabet
{(a,0.05), (b,0.05), (c,0.1), (d ,0.2), (e,0.3), (f ,0.2), (g,0.1)}.
(RMIT University) Greedy Techniques Lecture 9 53 / 61
– Example
0.20
0.10
0.05
0
0.05
1
0
0.10
1
0.20 0.30 0.30
0.20
0
0.10
1
a b
c
d e
f g
Construct a from the Alphabet
{(a,0.05), (b,0.05), (c,0.1), (d ,0.2), (e,0.3), (f ,0.2), (g,0.1)}.
(RMIT University) Greedy Techniques Lecture 9 54 / 61
– Example
0.40
0.20
0.10
0.05
0
0.05
1
0
0.10
1
0
0.20
1
0.30 0.30
0.20
0
0.10
1
a b
c
d
e
f g
Construct a from the Alphabet
{(a,0.05), (b,0.05), (c,0.1), (d ,0.2), (e,0.3), (f ,0.2), (g,0.1)}.
(RMIT University) Greedy Techniques Lecture 9 55 / 61
– Example
0.40
0.20
0.10
0.05
0
0.05
1
0
0.10
1
0
0.20
1
0.60
0.30
0
0.30
0.20
0
0.10
1
1
a b
c
d e
f g
Construct a from the Alphabet
{(a,0.05), (b,0.05), (c,0.1), (d ,0.2), (e,0.3), (f ,0.2), (g,0.1)}.
(RMIT University) Greedy Techniques Lecture 9 56 / 61
– Example
1.00
0.40
0.20
0.10
0.05
0
0.05
1
0
0.10
1
0
0.20
1
0
0.60
0.30
0
0.30
0.20
0
0.10
1
1
1
a b
c
d e
f g
Construct a from the Alphabet
{(a,0.05), (b,0.05), (c,0.1), (d ,0.2), (e,0.3), (f ,0.2), (g,0.1)}.
(RMIT University) Greedy Techniques Lecture 9 57 / 61
Symbol Codeword `i
a 0000 4
b 0001 4
c 001 3
d 01 2
e 10 2
f 110 3
g 111 3
The and the corresponding codeword lengths.
(RMIT University) Greedy Techniques Lecture 9 58 / 61
• This approach requires Θ(n log n) time if a min heap (priority
queue) is used to manage the set of candidates and their weights.
• If the input list is already sorted by their probabilities, then the
codes can be constructed in Θ(n) time.
(RMIT University) Greedy Techniques Lecture 9 59 / 61
Overview
1 Overview
2 Prim’s Algorithm
3 Kruskal’s Algorithm
4 Dijkstra’s Algorithm
5 Data Compression
6 Summary
(RMIT University) Greedy Techniques Lecture 9 60 / 61
Summary
• Understand and be able to apply the greedy approach to solving
problems.
• Examples:
• spanning tree – Prim’s algorithm
• spanning tree – Kruskal’s algorithm
• single source shortest-path – Dijkstra’s algoirthm
• data compression
(RMIT University) Greedy Techniques Lecture 9 61 / 61
Overview
Prim's Algorithm
Kruskal's Algorithm
Dijkstra's Algorithm
Data Compression
Summary