Program Analysis
Greedy Algorithms 1
David Weir (U of Sussex) Program Analysis Term 1, 2017 181 / 606
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, 2017 182 / 606
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, 2017 183 / 606
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, 2017 184 / 606
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, 2017 185 / 606
Interval Scheduling Example
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
David Weir (U of Sussex) Program Analysis Term 1, 2017 186 / 606
Interval Scheduling Example
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
a
d
e
h
David Weir (U of Sussex) Program Analysis Term 1, 2017 186 / 606
One for you to solve
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
David Weir (U of Sussex) Program Analysis Term 1, 2017 187 / 606
One for you to solve
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
c
d
g
h
David Weir (U of Sussex) Program Analysis Term 1, 2017 187 / 606
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, 2017 188 / 606
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, 2017 189 / 606
Weighted Interval Scheduling Example
time →
0 1 2 3 4 5 6 7 8 9 10
5
2
9
3
4
3
3
1
David Weir (U of Sussex) Program Analysis Term 1, 2017 190 / 606
Weighted Interval Scheduling Example
time →
0 1 2 3 4 5 6 7 8 9 10
5
2
9
3
4
3
3
1
9
4
1
David Weir (U of Sussex) Program Analysis Term 1, 2017 190 / 606
One for you to solve
time →
0 1 2 3 4 5 6 7 8 9 10
9
1
2
5
6
1
6
3
David Weir (U of Sussex) Program Analysis Term 1, 2017 191 / 606
One for you to solve
time →
0 1 2 3 4 5 6 7 8 9 10
9
1
2
5
6
1
6
3
2
5
6
David Weir (U of Sussex) Program Analysis Term 1, 2017 191 / 606
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, 2017 192 / 606
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, 2017 193 / 606
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, 2017 193 / 606
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, 2017 194 / 606
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, 2017 195 / 606
Independent Set
Input: a graph
Output: largest independent set: no two nodes joined by edge
v1
v2
v3
v4
v5
v6
v7
v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 196 / 606
Independent Set
Input: a graph
Output: largest independent set: no two nodes joined by edge
v1
v2
v3
v4
v5
v6
v7
v8v1
v4
v5
v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 196 / 606
One for you to solve
v1
v2
v3
v4
v5
v6
v7
v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 197 / 606
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, 2017 198 / 606
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, 2017 199 / 606
One for you to solve
15 12 7 1 23 12 6 17 14 5
David Weir (U of Sussex) Program Analysis Term 1, 2017 200 / 606
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, 2017 201 / 606
Greedy Algorithms:
The Interval Scheduling Problem
David Weir (U of Sussex) Program Analysis Term 1, 2017 202 / 606
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, 2017 203 / 606
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, 2017 204 / 606
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, 2017 205 / 606
Interval Scheduling Problem
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
Problem: to schedule as many of the intervals as possible
David Weir (U of Sussex) Program Analysis Term 1, 2017 206 / 606
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, 2017 207 / 606
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, 2017 208 / 606
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, 2017 209 / 606
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, 2017 210 / 606
Illustrating the Interval Scheduling Algorithm
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
First create priority queue Q, initialise A and set current time to 0
David Weir (U of Sussex) Program Analysis Term 1, 2017 211 / 606
Illustrating the Interval Scheduling Algorithm
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
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, 2017 212 / 606
Illustrating the Interval Scheduling Algorithm
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
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, 2017 213 / 606
Illustrating the Interval Scheduling Algorithm
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
Q = (c,d ,e, f ,g,h) A = {b}
Remove c from Q; c can be scheduled so add c to A and reset time
David Weir (U of Sussex) Program Analysis Term 1, 2017 214 / 606
Illustrating the Interval Scheduling Algorithm
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
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, 2017 215 / 606
Illustrating the Interval Scheduling Algorithm
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
Q = (e, f ,g,h) A = {b, c}
Remove e from Q; e can be scheduled so add e to A and reset time
David Weir (U of Sussex) Program Analysis Term 1, 2017 216 / 606
Illustrating the Interval Scheduling Algorithm
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
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, 2017 217 / 606
Illustrating the Interval Scheduling Algorithm
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
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, 2017 218 / 606
Illustrating the Interval Scheduling Algorithm
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
Q = (h) A = {b, c,e}
Remove h from Q; h can be scheduled so add h to A and reset time
David Weir (U of Sussex) Program Analysis Term 1, 2017 219 / 606
Illustrating the Interval Scheduling Algorithm
time →
0 1 2 3 4 5 6 7 8 9 10
a
b
c
d
e
f
g
h
Q = () A = {b, c,e,h}
Q is empty so all done!
David Weir (U of Sussex) Program Analysis Term 1, 2017 220 / 606
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, 2017 221 / 606
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, 2017 222 / 606
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, 2017 223 / 606
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, 2017 224 / 606
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, 2017 225 / 606
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, 2017 226 / 606
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, 2017 227 / 606
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, 2017 227 / 606
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, 2017 228 / 606
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, 2017 228 / 606
Question for you
Consider best-case and worst-case running times.
David Weir (U of Sussex) Program Analysis Term 1, 2017 229 / 606
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, 2017 229 / 606
Greedy Algorithms:
The Shortest Path Problem
David Weir (U of Sussex) Program Analysis Term 1, 2017 230 / 606
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, 2017 231 / 606 Example Graph v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 3 11 Consider the path (v5, v2, v1, v3) David Weir (U of Sussex) Program Analysis Term 1, 2017 232 / 606 Example Graph v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 3 11 Consider the path (v5, v2, v1, v3) David Weir (U of Sussex) Program Analysis Term 1, 2017 232 / 606 Example Graph v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 3 11 The weight of (v5, v2, v1, v3) is 2 + 3 + 2 = 7 David Weir (U of Sussex) Program Analysis Term 1, 2017 232 / 606 Example Graph v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 3 11 (v5, v2, v1, v3) is the shortest path from v5 to v3 David Weir (U of Sussex) Program Analysis Term 1, 2017 232 / 606 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, 2017 233 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s Suppose s = v7 and A = {v5, v7} David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s δ(v7) = 0 David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s δ(v5) = 15 David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s δ(v4) = 1 David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s δ(v2) = 17 David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s δ(v8) = 21 David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s For all other vertices v we have δ(v) = ∞ David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s Suppose we add v4 to A David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 sv4 Potentially changes values of δ for vertices adjacent to v4 David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 sv4 δ(v5) reduces to 12 David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 sv4 δ(v6) = 14 David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 sv4 δ(v7) isn’t improved David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 Example v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 sv4 But note that the value δ(v2) can be improved from 17 to 14 David Weir (U of Sussex) Program Analysis Term 1, 2017 234 / 606 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, 2017 235 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s What happens if we add v4 to A before v5 David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s δ(v7) = 0 David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s δ(v4) = 1 David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s δ(v5) = 12 David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s δ(v6) = 14 David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s For all other vertices v we have δ(v) = ∞ David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s Suppose we now add v5 to A David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s v5 Potentially changes values of δ for vertices adjacent to v5 David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s v5 δ(v5) can’t be improved David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s v5 δ(v7) can’t be improved David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s v5 δ(v2) = 14 David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s v5 δ(v8) = 18 David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 Example Reconsidered v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 8 13 11 s v5 This time it was sufficient just to consider vertices adjacent to v5 David Weir (U of Sussex) Program Analysis Term 1, 2017 236 / 606 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, 2017 237 / 606 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 add v to A for each {v ,u} ∈ E where u 6∈ A if δ(u) > δ(v) + w(v ,u) then
let δ(u) = δ(v) + w(v ,u)
David Weir (U of Sussex) Program Analysis Term 1, 2017 238 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
Initialise δ values
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞∞
∞
∞
0
∞
Initialise Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞∞
∞
∞
0
∞
(v7, v1, v2, v3, v4, v5, v6, v8)
Remove v7 from Q and add to A
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞∞
∞
∞
0
∞
(v1, v2, v3, v4, v5, v6, v8)
v7
Consider edge {v7, v4}
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞∞
∞
∞
0
∞
(v1, v2, v3, v4, v5, v6, v8)
v7
δ(v4) > δ(v7) + w(v7, v4) so update δ(v4)
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
∞
∞
0
∞
(v1, v2, v3, v4, v5, v6, v8)
v71
Reposition v4 in Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
∞
∞
0
∞ v71
(v4, v1, v2, v3, v5, v6, v8)
Consider edge {v7, v5}
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
∞
∞
0
∞ v71
(v4, v1, v2, v3, v5, v6, v8)
δ(v5) > δ(v7) + w(v7, v5) so update δ(v5)
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
∞
0
∞ v71
(v4, v1, v2, v3, v5, v6, v8)
15
Reposition v5 in Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
∞
0
∞ v71
15
(v4, v5, v1, v2, v3, v6, v8)
All vertices adjacent to v7 now considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
∞
0
∞ v71
15
(v4, v5, v1, v2, v3, v6, v8)
Remove v4 from Q and add to A
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
∞
0
∞ v71
15
(v5, v1, v2, v3, v6, v8)
v4
Consider edge {v4, v5}
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
∞
0
∞ v71
15
(v5, v1, v2, v3, v6, v8)
v4
δ(v5) > δ(v4) + w(v4, v5) so update δ(v5)
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
∞
0
∞ v71
(v5, v1, v2, v3, v6, v8)
v4
12
No need to reposition v5 in Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
∞
0
∞ v71
(v5, v1, v2, v3, v6, v8)
v4
12
Consider edge {v4, v6}
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
∞
0
∞ v71
(v5, v1, v2, v3, v6, v8)
v4
12
δ(v6) > δ(v4) + w(v4, v6) so update δ(v6)
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
0
∞ v71
(v5, v1, v2, v3, v6, v8)
v4
12
4
Reposition v6 in Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
0
∞ v71 v4
12
4 (v6, v5, v1, v2, v3, v8)
All vertices adjacent to v4 now considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
0
∞ v71 v4
12
4 (v6, v5, v1, v2, v3, v8)
Remove v6 from Q and add to A
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
0
∞ v71 v4
12
4 (v5, v1, v2, v3, v8)v6
Consider edge {v6, v3}
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
∞
0
∞ v71 v4
12
4 (v5, v1, v2, v3, v8)v6
δ(v3) > δ(v6) + w(v6, v3) so update δ(v3)
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
0
∞ v71 v4
12
4 (v5, v1, v2, v3, v8)v6
13
Reposition v3 in Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
0
∞ v71 v4
12
4 v6
13
(v5, v3, v1, v2, v8)
Consider edge {v6, v8}
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
0
∞ v71 v4
12
4 v6
13
(v5, v3, v1, v2, v8)
δ(v8) > δ(v6) + w(v6, v8) so update δ(v8)
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
0
v71 v4
12
4 v6
13
(v5, v3, v1, v2, v8)
8
Reposition v8 in Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
0
v71 v4
12
4 v6
138
(v8, v5, v3, v1, v2)
All vertices adjacent to v6 now considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
0
v71 v4
12
4 v6
138
(v8, v5, v3, v1, v2)
Remove v8 from Q and add to A
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
0
v71 v4
12
4 v6
138
(v5, v3, v1, v2)
v8
Consider edge {v8, v5}
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞∞
0
v71 v4
12
4 v6
138
(v5, v3, v1, v2)
v8
δ(v5) < δ(v8) + w(v8, v5) so don’t update δ(v5) David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s ∞∞ 0 v71 v4 12 4 v6 138 (v5, v3, v1, v2) v8 All vertices adjacent to v8 now considered David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s ∞∞ 0 v71 v4 12 4 v6 138 (v5, v3, v1, v2) v8 Remove v5 from Q and add to A David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s ∞∞ 0 v71 v4 12 4 v6 138 v8 (v3, v1, v2) v5 Consider edge {v5, v2} David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s ∞∞ 0 v71 v4 12 4 v6 138 v8 (v3, v1, v2) v5 δ(v2) > δ(v5) + w(v5, v2) so update δ(v2)
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞
0
v71 v4
12
4 v6
138 v8
(v3, v1, v2)
v5
14
Reposition v2 in Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞
0
v71 v4
12
4 v6
138 v8
v5
14
(v3, v2, v1)
All vertices adjacent to v5 now considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞
0
v71 v4
12
4 v6
138 v8
v5
14
(v3, v2, v1)
Remove v3 from Q and add to A
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞
0
v71 v4
12
4 v6
138 v8
v5
14
(v2, v1)
v3
Consider edge {v3, v1}
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
∞
0
v71 v4
12
4 v6
138 v8
v5
14
(v2, v1)
v3
δ(v1) > δ(v3) + w(v3, v1) so update δ(v1)
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
0
v71 v4
12
4 v6
138 v8
v5
14
(v2, v1)
v3
15
No need to reposition v1 in Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
0
v71 v4
12
4 v6
138 v8
v5
14
(v2, v1)
v3
15
Consider edge {v3, v2}
David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606
Illustration of Dijkstra’s Algorithm
v1v2
v3v4
v5
v6
v7v8
3
2
9
2
1
156
4 9
3
11
s
0
v71 v4
12
4 v6
138 v8
v5
14
(v2, v1)
v3
15
δ(v2) < δ(v3) + w(v3, v2) so don’t update δ(v2) David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s 0 v71 v4 12 4 v6 138 v8 v5 14 (v2, v1) v3 1515 All vertices adjacent to v3 now considered David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s 0 v71 v4 12 4 v6 138 v8 v5 14 (v2, v1) v3 15 Remove v2 from Q and add to A David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s 0 v71 v4 12 4 v6 138 v8 v5 14 v3 15 (v1) v2 Consider edge {v2, v1} David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s 0 v71 v4 12 4 v6 138 v8 v5 14 v3 15 (v1) v2 δ(v1) < δ(v2) + w(v2, v1) so don’t update δ(v1) David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s 0 v71 v4 12 4 v6 138 v8 v5 14 v3 15 (v1) v2 All vertices adjacent to v2 now considered David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s 0 v71 v4 12 4 v6 138 v8 v5 14 v3 15 (v1) v2 Remove v1 from Q and add to A David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s 0 v71 v4 12 4 v6 138 v8 v5 14 v3 15 v2 () v1 No vertices adjacent to v1 need to be considered David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Illustration of Dijkstra’s Algorithm v1v2 v3v4 v5 v6 v7v8 3 2 9 2 1 156 4 9 3 11 s 0 v71 v4 12 4 v6 138 v8 v5 14 v3 15 v2 () v1 Priority queue Q is empty — all done! David Weir (U of Sussex) Program Analysis Term 1, 2017 239 / 606 Problem for you Run Dijkstra’s Algorithm on this graph with s = v1 v1 v2 v3 v4 v5 9 2 8 6 1 2 2 5 David Weir (U of Sussex) Program Analysis Term 1, 2017 240 / 606 Problem for you Run Dijkstra’s Algorithm on this graph with s = v1 v1 v2 v3 v4 v5 9 2 8 6 1 2 2 5 δ(v1) = 0, δ(v2) = 7, δ(v3) = 2, δ(v4) = 4, δ(v5) = 6 David Weir (U of Sussex) Program Analysis Term 1, 2017 240 / 606 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, 2017 241 / 606 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, 2017 242 / 606 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, 2017 243 / 606 Proving Correctness of Dijkstra’s Algorithm A s x u v Q David Weir (U of Sussex) Program Analysis Term 1, 2017 244 / 606 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, 2017 245 / 606 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 add v to A for each {v ,u} ∈ E where u 6∈ A if δ(u) > δ(v) + w(v ,u) then
let δ(u) = δ(v) + w(v ,u)
David Weir (U of Sussex) Program Analysis Term 1, 2017 246 / 606
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, 2017 247 / 606
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, 2017 248 / 606
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, 2017 248 / 606
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, 2017 249 / 606
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, 2017 249 / 606