Greedy Algorithms 1
David Weir (U of Sussex) Program Analysis Term 1, 2015 182 / 192
Horses for Courses
Different problem solving strategies suite different kinds of problems
Greedy method Dynamic Programming Network Flow
David Weir (U of Sussex) Program Analysis Term 1, 2015 183 / 192
Five Representative Problems
Different strategies suitable for different problems
Consider 5 example problems that exhibit some of the possibilities
◮ interval scheduling
◮ weighted interval scheduling
◮ bipartite matching
◮ independent set
◮ competitive facility location
David Weir (U of Sussex) Program Analysis Term 1, 2015 184 / 192
Problem 1: The Interval Scheduling Problem
The idea:
Some resource is available
Set of intervals that can be scheduled
Each interval has fixed start and end time
Goal is to schedule as many of the intervals as possible Resource can only be applied to one interval at a time
David Weir (U of Sussex) Program Analysis Term 1, 2015 185 / 192
Specifying the Problem
Two intervals are compatible if they have non-overlapping intervals Input: A set of intervals where each interval has a start and end time Output: The largest selection of compatible intervals that can be made
David Weir (U of Sussex) Program Analysis Term 1, 2015 186 / 192
Interval Scheduling Example
a
b
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 187 / 192
Interval Scheduling Example
a
b
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 187 / 192
One for you to solve
b
a
c
d
e
g
f
h
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 188 / 192
One for you to solve
c
b
a
d
e
g
f
h
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 188 / 192
Greedy Interval Scheduling
Can be solved using the so-called greedy approach make series of locally best choices
very efficient way to solve problems
be greedy when you can get away with it
can’t always get away with it
some problems not amenable to greedy approach to be continued…
David Weir (U of Sussex) Program Analysis Term 1, 2015 189 / 192
Problem 2: Weighted Interval Scheduling
A variant of the Interval Scheduling Problem Each interval has been assigned a weight
This could be a measure of how important it is that the interval is scheduled
Input: set of intervals with start and finish times plus weights Output: subset of compatible intervals with greatest total weight
Note that the number of intervals chosen is not important
David Weir (U of Sussex) Program Analysis Term 1, 2015 190 / 192
Weighted Interval Scheduling Example
5
2
9
3
4
3
3
1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 191 / 192
Weighted Interval Scheduling Example
5
2
9
3
4
3
3
1
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 191 / 192
One for you to solve
1
9
2
5
6
6
1
3
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 192 / 192
One for you to solve
9
1
2
5
6
1
6
3
0 1 2 3 4 5 6 7 8 9 10 time →
David Weir (U of Sussex) Program Analysis Term 1, 2015 192 / 192
Solving Weighted Interval Scheduling
Cannot be solved using the greedy approach
Requires the more powerful technique of dynamic programming systematically decompose problems into subproblems
based on divide-and-conquer approach
solutions to subproblems recorded in table
to be continued…
David Weir (U of Sussex) Program Analysis Term 1, 2015 193 / 192
Bipartite Matching
Input: a graph that is bipartite (leave details of definition for later) Output: matching with most edges possible
x1 x2 x3 x4 x5
y1 y2 y3 y4 y5
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
194 / 192
Bipartite Matching
Input: a graph that is bipartite (leave details of definition for later) Output: matching with most edges possible
x1 x2 x3 x4 x5
y1 y2 y3 y4 y5
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
194 / 192
One for you to solve
Input: a graph that is bipartite (leave details of definition for later) Output: matching with most edges possible
x1 x2 x3 x4 x5
y1 y2 y3 y4 y5
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
195 / 192
Bipartite Matching
Can be solved using the so-called network flow approach Bipartite matching problem can be seen as special case of
network flow problem
Network flow problem widely applicable More later…
David Weir (U of Sussex) Program Analysis Term 1, 2015 196 / 192
Independent Set
Input: a graph
Output: largest independent set: no two nodes joined by edge
v2 v4 v6
v1 v8
v3 v5 v7
David Weir (U of Sussex) Program Analysis Term 1, 2015 197 / 192
Independent Set
Input: a graph
Output: largest independent set: no two nodes joined by edge
v2 v4 v6
v1
v8
v3 v5 v7
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
197 / 192
One for you to solve
v2 v4 v6
v1 v8
v3 v5 v7
David Weir (U of Sussex) Program Analysis Term 1, 2015 198 / 192
Independent Set
NP-complete problem
no efficient algorithm known that solves this problem exponential number of subsets to consider
David Weir (U of Sussex) Program Analysis Term 1, 2015 199 / 192
Competitive Facility Location
Input: A graph with weighted nodes
Output: Players alternate choosing nodes, but can’t select node when neighbouring node has already been chosen
Goal is to maximise weight of selected nodes
10 1 5 15 5 1 5 1 15 10
Second player can’t exceed total node weight of 20
David Weir (U of Sussex) Program Analysis Term 1, 2015 200 / 192
One for you to solve
15 12 7 1 23 12 6 17 14 5
David Weir (U of Sussex) Program Analysis Term 1, 2015 201 / 192
Competitive Facility Location
P-SPACE-complete problem
Even harder than NP-complete
Compare difficulty in verifying that solution is valid Seems to requires polynomial space
David Weir (U of Sussex) Program Analysis Term 1, 2015 202 / 192
Greedy Algorithms:
The Interval Scheduling Problem
David Weir (U of Sussex) Program Analysis Term 1, 2015 203 / 192
Summary
What makes an algorithm a greedy algorithm Interval Scheduling Problem
Shortest Path Problem
Minimum Spanning Tree Problem Construction of Huffman Codes
David Weir (U of Sussex) Program Analysis Term 1, 2015 204 / 192
The Greedy Approach
An approximate characterisation:
The algorithm makes a series of choices
A solution is built up as these choices are made The locally best option is made at each stage
When is this approach appropriate?
David Weir (U of Sussex) Program Analysis Term 1, 2015 205 / 192
When Greed Works
No need to worry about what will happen in the future Safe to commit to each decision
No backtracking on decisions
Guarantee that the globally best solution will be found
Some problems are amenable to this approach while others aren’t
David Weir (U of Sussex) Program Analysis Term 1, 2015 206 / 192
Interval Scheduling Problem
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
Problem: to schedule as many of the intervals as possible
David Weir (U of Sussex) Program Analysis Term 1, 2015 207 / 192
The Series of Choices
Setting up the approach:
Working from time 0 forward in time
Decisions involving choosing which of the intervals to schedule next
Question: On what basis can the choice be made?
Possible Strategy: Choose the interval that can be started earliest
Does this guarantee that an optimal solution is found?
David Weir (U of Sussex) Program Analysis Term 1, 2015 208 / 192
A Non-optimal Strategy
Choosing first available interval is a bad strategy
A very long interval could be chosen
See interval a in previous example
Could be better to choose a shorter interval that ends earlier In this case better to choose interval b
Problem with this strategy is we are only counting total number of intervals scheduled
David Weir (U of Sussex) Program Analysis Term 1, 2015 209 / 192
A Better Strategy
Among those intervals that could be scheduled next, choose the interval with the earliest possible ending point
An interval can be scheduled if the start time has not yet passed Use a priority queue to hold the intervals
Use the interval’s end time as its priority
Earlier end times have higher priority than later ones
For an interval α let s(α) and f(α) be the start and finish times of α, respectively
David Weir (U of Sussex) Program Analysis Term 1, 2015 210 / 192
Interval Scheduling Algorithm
IntervalSchedule(I) :
let Q be queue of intervals prioritised by ealiest end time initialise A, the set of scheduled intervals, to be the empty set initialise current time k to be 0
while Q is not yet empty
remove interval α from the front of Q if k ≤ s(α) then
add the interval α to the set A
set the current time k to be f (α) return A
David Weir (U of Sussex) Program Analysis Term 1, 2015 211 / 192
Illustrating the Interval Scheduling Algorithm
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
First create priority queue Q, initialise A and set current time to 0
David Weir (U of Sussex) Program Analysis Term 1, 2015 212 / 192
Illustrating the Interval Scheduling Algorithm
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
Q = (b,a,c,d,e,f,g,h) A = {}
Remove b from Q; b can be scheduled so add b to A and reset time
David Weir (U of Sussex) Program Analysis Term 1, 2015 213 / 192
Illustrating the Interval Scheduling Algorithm
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
Q = (a,c,d,e,f,g,h) A = {b} Remove a from Q, but too late to schedule a
David Weir (U of Sussex) Program Analysis
Term 1, 2015
214 / 192
Illustrating the Interval Scheduling Algorithm
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
Q = (c,d,e,f,g,h)
Remove c from Q; c can be scheduled so add c to A and reset time
A = {b}
David Weir (U of Sussex) Program Analysis Term 1, 2015 215 / 192
Illustrating the Interval Scheduling Algorithm
a
b
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
Q = (d,e,f,g,h) A = {b,c} Remove d from Q, but too late to schedule d
David Weir (U of Sussex) Program Analysis Term 1, 2015 216 / 192
Illustrating the Interval Scheduling Algorithm
a
b
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
Q = (e,f,g,h)
Remove e from Q; e can be scheduled so add e to A and reset time
A = {b,c}
David Weir (U of Sussex) Program Analysis Term 1, 2015 217 / 192
Illustrating the Interval Scheduling Algorithm
a
b
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
Q = (f,g,h) A = {b,c,e} Remove f from Q, but too late to schedule f
David Weir (U of Sussex) Program Analysis Term 1, 2015 218 / 192
Illustrating the Interval Scheduling Algorithm
a
b
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
Q = (g,h) A = {b,c,e} Remove g from Q, but too late to schedule g
David Weir (U of Sussex) Program Analysis Term 1, 2015 219 / 192
Illustrating the Interval Scheduling Algorithm
a
b
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
Q = (h)
Remove h from Q; h can be scheduled so add h to A and reset time
A = {b,c,e}
David Weir (U of Sussex) Program Analysis Term 1, 2015 220 / 192
Illustrating the Interval Scheduling Algorithm
a
b
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 time →
Q = () A = {b,c,e,h} Q is empty so all done!
David Weir (U of Sussex) Program Analysis Term 1, 2015 221 / 192
Correctness of Algorithm
All intervals in A are compatible The intervals do not overlap
This is guaranteed by the fact that we check that the start time of each interval is not before the end time of the one previously scheduled
David Weir (U of Sussex) Program Analysis Term 1, 2015 222 / 192
Correctness of Algorithm (cont.)
We will show that for any optimal solution B we know that |A| = |B| A is as good as any optimal solution
We will show that the solution A keeps ahead of any optimal solution B.
Consider some optimal solution B
Let (α1, . . . , αk ) be the elements of A in scheduled order Let (β1, . . . , βm) be the elements of B in scheduled order
David Weir (U of Sussex) Program Analysis Term 1, 2015 223 / 192
Correctness of Algorithm (cont.)
Claim: A stays ahead of B
f (αi ) ≤ f (βi ) for all i such that 1 ≤ i ≤ k
Proof by induction on i:
Basis of induction: clearly true for i = 1
Inductive step:
intervals in B are compatible so f(βi−1) ≤ s(βi) by induction f(αi−1) ≤ f(βi−1)
so f(αi−1) ≤ s(βi)
so βi was available to be scheduled when αi was so f(αi) ≤ f(βi)
David Weir (U of Sussex) Program Analysis Term 1, 2015 224 / 192
Correctness of Algorithm (cont.)
Claim: A is as good as B
Proof by contradiction
Suppose B is better than A
Must be more elements in B than A, so m > k
Because A stays ahead of B we know that f(αk) ≤ f(βk)
So the algorithm would have included βk+1 in A
Since βk+1 is compatible with βk it must be compatible with αk
David Weir (U of Sussex) Program Analysis Term 1, 2015 225 / 192
Interval Scheduling Algorithm
IntervalSchedule(I) :
let Q be the priority queue containing all intervals in I initialise A, the set of scheduled intervals, to be the empty set initialise current time k to be 0
while Q is not yet empty
remove interval α from the front of Q if k ≤ s(α) then
add the interval α to the set A
set the current time k to be f (α) return A
David Weir (U of Sussex) Program Analysis Term 1, 2015 226 / 192
Analysis of Running Time
What is a good measure of progress
Number of intervals that have been considered Always increases by one each time loop is executed Limits number of executions of loop to n
Suppose priority queue implemented as a heap O(n) to build initially
O(log n) to remove an item
Each iteration therefore takes O(log n)
All n iterations take O(n log n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 227 / 192
Question for you
Is it correct to say that the running time of the algorithm is Θ(n log n)?
David Weir (U of Sussex) Program Analysis Term 1, 2015 228 / 192
Question for you
Is it correct to say that the running time of the algorithm is Θ(n log n)?
No. Consider the case where all intervals end at same time. The body of loop takes constant time because removal from heap never involves any exchanges.
David Weir (U of Sussex) Program Analysis Term 1, 2015 228 / 192
Question for you
What would the running time of the algorithm be if we implement the priority queue as an unsorted list?
David Weir (U of Sussex) Program Analysis Term 1, 2015 229 / 192
Question for you
What would the running time of the algorithm be if we implement the priority queue as an unsorted list?
Running time would be O(n2) since it would take O(n) time to find highest priority element
David Weir (U of Sussex) Program Analysis Term 1, 2015 229 / 192
Question for you
Consider best-case and worst-case running times.
David Weir (U of Sussex) Program Analysis Term 1, 2015 230 / 192
Question for you
Consider best-case and worst-case running times. heap: Best-case O(n), worst-case O(n log n)
unsorted list: Best-case O(n), worst-case O(n2)
David Weir (U of Sussex) Program Analysis Term 1, 2015 230 / 192
Greedy Algorithms: The Shortest Path Problem
David Weir (U of Sussex) Program Analysis Term 1, 2015 231 / 192
Shortest Path Problem
Problem: Given a weighted graph G = (V , E ), an edge weight function w and some s ∈ V the goal is to find the length of the shortest path to each vertex in V
Definitions:
A path p is a sequence of vertices p = (v1,…,vk) where
{vi,vi+1} ∈ E for all i such that 1 ≤ i < k
The weight of a path is the sum of the weights of the edges on
the path
The distance of a vertex v from s is the weight of the shortest
(least weighted) path from s to v
Note that we will assume that all edge weights are positive
David Weir (U of Sussex) Program Analysis Term 1, 2015 232 / 192
Example Graph
v2v3v 521
15
11 2
9
vv1vv 8473
6
3 v6
Consider the path (v5, v2, v1, v3)
4
8
David Weir (U of Sussex) Program Analysis Term 1, 2015 233 / 192
Example Graph
v2v3v 521
15
11 2
9
vv1vv 8473
6
3 v6
Consider the path (v5, v2, v1, v3)
4
8
David Weir (U of Sussex) Program Analysis Term 1, 2015 233 / 192
Example Graph
v2v3v 521
15
11 2
9
vv1vv 8473
6
4
3 v6
8
The weight of (v5, v2, v1, v3) is 2 + 3 + 2 = 7
David Weir (U of Sussex) Program Analysis Term 1, 2015 233 / 192
Example Graph
v2v3v 521
15
11 2
9
vv1vv 8473
6
4
3 v6
8
(v5, v2, v1, v3) is the shortest path from v5 to v3
David Weir (U of Sussex) Program Analysis Term 1, 2015 233 / 192
A Greedy Algorithm
The underlying algorithm
Vertices added to a set A once their distance from s established
For vertices v not yet in A we keep track of δ(v): the shortest distance from s to v routed only through vertices that are already in A
David Weir (U of Sussex) Program Analysis Term 1, 2015 234 / 192
Example
v2v3v 521
15
11 2
9
vv1vsv 8473
6
4
13 v6
8
Suppose s = v7 and A = {v5,v7}
David Weir (U of Sussex) Program Analysis Term 1, 2015 235 / 192
Example
v2v3v 521
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v7) = 0
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
235 / 192
Example
v2v3v 521
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v5) = 15
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
235 / 192
Example
v2v3v 521
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v4) = 1
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
235 / 192
Example
v2v3v 521
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v2) = 17
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
235 / 192
Example
v2v3v 521
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v8) = 21
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
235 / 192
Example
v2v3v 521
15
11 2
9
vv1vsv 8473
6
4
13 v6
8
For all other vertices v we have δ(v) = ∞
David Weir (U of Sussex) Program Analysis Term 1, 2015 235 / 192
Example
v2v3v 521
15
11 2
9
vv1vsv 8473
6
13 v6
Suppose we add v4 to A David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
235 / 192
Example
v2v3v 521
15
11 2
9
v v 1 v s v 8 4 7 3
6
4
13 v6
8
Potentially changes values of δ for vertices adjacent to v4
David Weir (U of Sussex) Program Analysis Term 1, 2015 235 / 192
Example
v2v3v 521
15
11 2
9
v v 1 v s v 8 4 7 3
6
13 v6
δ(v5) reduces to 12 David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
235 / 192
Example
v2v3v 521
15
11 2
9
v v 1 v s v 8 4 7 3
6
13 v6
δ(v6) = 14
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
235 / 192
Example
v2v3v 521
15
11 2
9
v v 1 v s v 8 4 7 3
6
13 v6
δ(v7) isn’t improved David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
235 / 192
Example
v2v3v 521
15
11 2
9
v v 1 v s v 8 4 7 3
6
4
13 v6
8
But note that the value δ(v2) can be improved from 17 to 14
David Weir (U of Sussex) Program Analysis Term 1, 2015 235 / 192
Building up A
The order we add vertices to A is crucial
We must add vertices in order of increasing distance from s We will only need to consider δ values for vertices not yet in A
David Weir (U of Sussex) Program Analysis Term 1, 2015 236 / 192
Example Reconsidered
v2v3v 521
15
11 2
9
vv1vsv 8473
6
4
13 v6
8
What happens if we add v4 to A before v5
David Weir (U of Sussex) Program Analysis Term 1, 2015 237 / 192
Example Reconsidered
v2v3v 521
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v7) = 0
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
237 / 192
Example Reconsidered
v2v3v 521
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v4) = 1
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
237 / 192
Example Reconsidered
v2v3v 521
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v5) = 12
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
237 / 192
Example Reconsidered
v2v3v 521
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v6) = 14
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
237 / 192
Example Reconsidered
v2v3v 521
15
11 2
9
vv1vsv 8473
6
4
13 v6
8
For all other vertices v we have δ(v) = ∞
David Weir (U of Sussex) Program Analysis Term 1, 2015 237 / 192
Example Reconsidered
v2v3v 521
15
11 2
9
vv1vsv 8473
6
13 v6
Suppose we now add v5 to A David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
237 / 192
Example Reconsidered
v 2 v 3 v 5 2 1
15
11 2
9
vv1vsv 8473
6
4
13 v6
8
Potentially changes values of δ for vertices adjacent to v5
David Weir (U of Sussex) Program Analysis Term 1, 2015 237 / 192
Example Reconsidered
v 2 v 3 v 5 2 1
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v5) can’t be improved David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
237 / 192
Example Reconsidered
v 2 v 3 v 5 2 1
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v7) can’t be improved David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
237 / 192
Example Reconsidered
v 2 v 3 v 5 2 1
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v2) = 14
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
237 / 192
Example Reconsidered
v 2 v 3 v 5 2 1
15
11 2
9
vv1vsv 8473
6
13 v6
δ(v8) = 18
David Weir (U of Sussex)
4
8
Program Analysis
Term 1, 2015
237 / 192
Example Reconsidered
v 2 v 3 v 5 2 1
15
11 2
9
vv1vsv 8473
6
4
13 v6
8
This time it was sufficient just to consider vertices adjacent to v5
David Weir (U of Sussex) Program Analysis Term 1, 2015 237 / 192
Prioritising Vertices
Use a priority queue prioritised by δ values
We need to select vertices in order of distance from s
We can use δ values for this
Some δ values will need updating
δ value for vertices or vertex nearest to s can’t be improved These can safely be added to A
We’ll prove this later!
David Weir (U of Sussex) Program Analysis Term 1, 2015 238 / 192
Dijkstra’s Algorithm
Dijkstra(G,w,s):
let A be the empty set
let δ(s) = 0
let δ(v) = ∞ for v ∈ V − {s}
let Q be a priority queue containing elements of V while Q is not empty
remove v from front of priority queue Q addv toA
for each {v,u} ∈ E where u ̸∈ A
if δ(u) > δ(v) + w(v,u) then let δ(u) = δ(v) + w(v,u)
David Weir (U of Sussex) Program Analysis Term 1, 2015 239 / 192
Illustration of Dijkstra’s Algorithm
v2v3v 521
15
11 2
9
vv1vsv 8473
6
3 v6
Initialise δ values David Weir (U of Sussex)
4
9
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
∞∞∞
v2v3v 521
15
11 2
9
∞v∞v1vsv∞ 8473
6
0
3 ∞ v6
Initialise Q
David Weir (U of Sussex)
4
9
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
∞∞∞
v2v3v 521
15
11 2
9
∞v∞v1vsv∞ 8473
6
0
3
∞ v6 (v7, v1, v2, v3, v4, v5, v6, v8)
Remove v7 from Q and add to A
4
9
David Weir (U of Sussex) Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
∞∞∞
v2v3v 521
15
11 2
9
∞v∞v1vs v∞ 8 4 7 3
6
0
4
3
9
(v1, v2, v3, v4, v5, v6, v8)
∞ v6 Consider edge {v7,v4}
David Weir (U of Sussex)
Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
∞∞∞
v2v3v 521
15
11 2
9
∞v∞v1vs v∞ 8 4 7 3
6
0
4
3
9
∞ v6
δ(v4) > δ(v7) + w(v7, v4) so update δ(v4)
(v1, v2, v3, v4, v5, v6, v8)
David Weir (U of Sussex) Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
∞∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
∞ v6 Reposition v4 in Q
3
9
(v1, v2, v3, v4, v5, v6, v8)
David Weir (U of Sussex)
Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
∞∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
3
9
(v4, v1, v2, v3, v5, v6, v8)
∞ v6 Consider edge {v7,v5}
David Weir (U of Sussex)
Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
∞∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
3
9
∞ v6
δ(v5) > δ(v7) + w(v7, v5) so update δ(v5)
(v4, v1, v2, v3, v5, v6, v8)
David Weir (U of Sussex) Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
15
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
∞ v6 Reposition v5 in Q
3
9
(v4, v1, v2, v3, v5, v6, v8)
David Weir (U of Sussex)
Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
15
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
3
9
∞ v6
All vertices adjacent to v7 now considered
(v4, v5, v1, v2, v3, v6, v8)
David Weir (U of Sussex) Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
15
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
3
∞ v6 (v4, v5, v1, v2, v3, v6, v8)
Remove v4 from Q and add to A
4
9
David Weir (U of Sussex) Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
15
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
3
9
(v5, v1, v2, v3, v6, v8)
∞ v6 Consider edge {v4,v5}
David Weir (U of Sussex)
Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
15
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
3
9
∞ v6
δ(v5) > δ(v4) + w(v4, v5) so update δ(v5)
(v5, v1, v2, v3, v6, v8)
David Weir (U of Sussex) Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
3
9
(v5, v1, v2, v3, v6, v8)
∞ v6
No need to reposition v5 in Q
David Weir (U of Sussex)
Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
3
9
(v5, v1, v2, v3, v6, v8)
∞ v6 Consider edge {v4,v6}
David Weir (U of Sussex)
Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
3
9
∞ v6
δ(v6) > δ(v4) + w(v4, v6) so update δ(v6)
(v5, v1, v2, v3, v6, v8)
David Weir (U of Sussex) Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
4 v6 Reposition v6 in Q
3
9
(v5, v1, v2, v3, v6, v8)
David Weir (U of Sussex)
Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
3
9
4 v6
(v6, v5, v1, v2, v3, v8) All vertices adjacent to v4 now considered
David Weir (U of Sussex) Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
3
4 v6 (v6, v5, v1, v2, v3, v8)
Remove v6 from Q and add to A
4
9
David Weir (U of Sussex) Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
3
9
4 v6 Consider edge {v6,v3}
(v5, v1, v2, v3, v8)
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
∞vv1vs v∞
9 814 7 3
0
4
3
9
4 v6
δ(v3) > δ(v6) + w(v6, v3) so update δ(v3)
(v5, v1, v2, v3, v8)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
∞v v 1 v s v
9
814 7 313
0
4
4 v6 Reposition v3 in Q
3
9
(v5, v1, v2, v3, v8)
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
∞v v 1 v s v
9
814 7 313
0
4
3
9
4 v6 Consider edge {v6,v8}
(v5, v3, v1, v2, v8)
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
∞v v 1 v s v
9
814 7 313
0
4
3
9
4 v6
δ(v8) > δ(v6) + w(v6, v8) so update δ(v8)
(v5, v3, v1, v2, v8)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
4 v6 Reposition v8 in Q
3
9
(v5, v3, v1, v2, v8)
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
3
9
4 v6
All vertices adjacent to v6 now considered
(v8, v5, v3, v1, v2)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
3
9
4 v6
Remove v8 from Q and add to A
(v8, v5, v3, v1, v2)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
3
9
4 v6 Consider edge {v8,v5}
(v5, v3, v1, v2)
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
3
9
4 v6
(v5, v3, v1, v2) δ(v5) < δ(v8) + w(v8, v5) so don’t update δ(v5)
David Weir (U of Sussex) Program Analysis Term 1, 2015 240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
3
9
4 v6
All vertices adjacent to v8 now considered
(v5, v3, v1, v2)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v2v3v 521
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
3
9
4 v6
Remove v5 from Q and add to A
(v5, v3, v1, v2)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
3
9
4 v6 Consider edge {v5,v2}
(v3,v1,v2)
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12
∞∞
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
3
9
4 v6
δ(v2) > δ(v5) + w(v5, v2) so update δ(v2)
(v3,v1,v2)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14
∞
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
4 v6 Reposition v2 in Q
3
9
(v3,v1,v2)
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14
∞
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
3
9
4 v6
All vertices adjacent to v5 now considered
(v3,v2,v1)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14
∞
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
9 8814 7 313
0
4
3
9
4 v6
Remove v3 from Q and add to A
(v3,v2,v1)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14
∞
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6 Consider edge {v3,v1}
(v2,v1)
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14
∞
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6
δ(v1) > δ(v3) + w(v3, v1) so update δ(v1)
(v2,v1)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14 15
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6
No need to reposition v1 in Q
(v2,v1)
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14 15
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6 Consider edge {v3,v2}
(v2,v1)
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14 15
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6
δ(v2) < δ(v3) + w(v3, v2) so don’t update δ(v2)
(v2,v1)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14 15
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6
All vertices adjacent to v3 now considered
(v2,v1)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14 15
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6
Remove v2 from Q and add to A
(v2,v1)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14 15
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6 Consider edge {v2,v1}
(v1)
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14 15
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6
δ(v1) < δ(v2) + w(v2, v1) so don’t update δ(v1)
(v1)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14 15
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6
All vertices adjacent to v2 now considered
(v1)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14 15
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6
Remove v1 from Q and add to A
(v1)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14 15
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6
No vertices adjacent to v1 need to be considered
()
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Illustration of Dijkstra’s Algorithm
12 14 15
v 2 v 3 v 5 2 1
15
11 2
6
v v 1 v s v
0
9
8 8
1 4
7
3 13
4
3
9
4 v6
Priority queue Q is empty — all done!
()
David Weir (U of Sussex) Program Analysis
Term 1, 2015
240 / 192
Problem for you
Run Dijkstra’s Algorithm on this graph with s = v1 v2
91 6
v2v5v 135
2 82
v4
David Weir (U of Sussex) Program Analysis Term 1, 2015 241 / 192
Problem for you
Run Dijkstra’s Algorithm on this graph with s = v1 v2
961
v2v5v 135
2 82
v4
δ(v1) = 0, δ(v2) = 7, δ(v3) = 2, δ(v4) = 4, δ(v5) = 6
David Weir (U of Sussex) Program Analysis Term 1, 2015 241 / 192
Proving Correctness of Dijkstra’s Algorithm
Claim: As each v is added to A, δ(v) is correct distance of v from s
Proof by contradiction:
Suppose that v is first vertex added to A with wrong δ(v) Let p be a shortest path from s to v
So we know that w(p) < δ(v)
David Weir (U of Sussex) Program Analysis Term 1, 2015 242 / 192
Proving Correctness of Dijkstra’s Algorithm
Another Claim: p must include a vertex not yet in A
Proof by contraction:
Suppose that p only includes vertices in A
Let u be the vertex immediately before v on the path p
δ(u) must be correct since v was first vertex with wrong value We would have had δ(v) = δ(u) + w(u, v)
So δ(v) would then had correct value w(p)
Yet later (when v added to A) w(p) < δ(v)
Impossible: value of δ(v) can’t go up!
David Weir (U of Sussex) Program Analysis Term 1, 2015 243 / 192
Proving Correctness of Dijkstra’s Algorithm
Return to previous proof
Established that p includes a vertex not in A Let u be the first vertex in p not in A
Let x immediately precede u in p
Time for a picture
David Weir (U of Sussex) Program Analysis Term 1, 2015 244 / 192
Proving Correctness of Dijkstra’s Algorithm
A
Q
v
u
sx
David Weir (U of Sussex) Program Analysis
Term 1, 2015 245 / 192
Proving Correctness of Dijkstra’s Algorithm
Continuing proof
δ(x) must be correct
When x was added to A we would have δ(u) = δ(x) + w(x, u) But δ(u) < w(p) because u appears inside path p
So δ(u) < δ(v) because we know that w(p) < δ(v)
So we would have added u not v to A
Contradiction!
David Weir (U of Sussex) Program Analysis Term 1, 2015 246 / 192
Dijkstra’s Algorithm
Dijkstra(G,w,s):
let A be the empty set
let δ(s) = 0
let δ(v) = ∞ for v ∈ V − {s}
let Q be a priority queue containing elements of V while Q is not empty
remove v from front of priority queue Q addv toA
for each {v,u} ∈ E where u ̸∈ A
if δ(u) > δ(v) + w(v,u) then let δ(u) = δ(v) + w(v,u)
David Weir (U of Sussex) Program Analysis Term 1, 2015 247 / 192
Running time of Dijkstra’s Algorithm
Initialisation of Q takes O(n) time
Measure of progress is number of vertices in A
Loop is executed n times
Each iteration involves at most outdegree(v) updates of δ values Total of m updates of δ values over all iterations
Each update of a δ value takes O(log n) steps
Total running time is O(m log n)
Can also be written O(n2 log n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 248 / 192
Question for you
What would the running time of Dijkstra’s Algorithm be if the priority queue is implemented with an unsorted list?
David Weir (U of Sussex) Program Analysis Term 1, 2015 249 / 192
Question for you
What would the running time of Dijkstra’s Algorithm be if the priority queue is implemented with an unsorted list?
There would be n iterations of while loop with O(n) per iteration. So total running time would be O(n2).
David Weir (U of Sussex) Program Analysis Term 1, 2015 249 / 192
Question for you
Precisely specify the loop invariant of Dijsktra’s Algorithm.
In particular, specify the value δ(v) for vertices v that are still in Q. Recall that the set of vertices that are no longer in Q is denoted A.
David Weir (U of Sussex) Program Analysis Term 1, 2015 250 / 192
Question for you
Precisely specify the loop invariant of Dijsktra’s Algorithm.
In particular, specify the value δ(v) for vertices v that are still in Q. Recall that the set of vertices that are no longer in Q is denoted A.
See earlier slides
David Weir (U of Sussex) Program Analysis Term 1, 2015 250 / 192