程序代写代做代考 algorithm Program Analysis

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