I need some help with some of my homework. When answering the questions, use these lecture notes,


Page
9
of 84
CS3000: Algorithms & Data
Unit 4: Shortest Paths (in Weighted Graphs)
a. Dijkstra’s Algorithm
Weighted Graphs
• Definition: A weighted graph 𝐺 = 𝑉, 𝐸, {𝑤(𝑒)}
• 𝑉 is the set of vertices
• 𝐸 ⊆ 𝑉 × 𝑉 is the set of edges
• 𝑤(𝑒) ∈ ℝ are edge weights
• Can be directed or undirected
• Today:
• Directed graphs (one-way streets)
• Non-negative edge weights (𝑤(𝑒) ≥ 0)
Shortest Paths
• In weighted graphs, the length of a path 𝑃 =
𝑣1 − 𝑣2 − ⋯ − 𝑣𝑘 is the sum of its edge weights:
• The distance 𝑑 𝑠, 𝑡 is the length of the shortest
path from 𝑠 to 𝑡
• Shortest Path: given nodes 𝑠, 𝑡 ∈ 𝑉, find the
shortest path from 𝑠 to 𝑡
• Single-Source Shortest Paths: given a node 𝑠 ∈ 𝑉,
find the shortest paths from 𝑠 to every 𝑡 ∈ 𝑉
• All-Pairs Shortest Paths: find the shortest path
between every (𝑠, 𝑡) ∈ 𝑉
Structure of Shortest Paths
• If 𝑢, 𝑣 ∈ 𝐸, then 𝑑 𝑠, 𝑣 ≤ 𝑑 𝑠, 𝑢 + 𝑤 𝑢, 𝑣 for
every node 𝑠 ∈ 𝑉
• If 𝑢, 𝑣 ∈ 𝐸, and 𝑑 𝑠, 𝑣 = 𝑑 𝑠, 𝑢 + 𝑤(𝑢, 𝑣) then
there is a shortest 𝑠 ↝ 𝑣-path ending with (𝑢, 𝑣)
Dijkstra’s Algorithm
• Dijkstra’s Shortest Path Algorithm is a modification
of BFS for non-negatively weighted graphs
• Informal Version:
• Maintain a set 𝑿 of explored nodes
• Maintain an upper bound on distance for all unexplored
nodes
• If 𝑢 is explored, then we know 𝑑(𝑠, 𝑢) (Key Invariant)
• If 𝑢 is explored, and (𝑢, 𝑣) is an edge, then we know
𝑑 𝑠, 𝑣 ≤ 𝑑 𝑠, 𝑢 + 𝑤 𝑢, 𝑣
• Explore the “closest” unexplored node
• Repeat until we’re done
Dijkstra’s Algorithm: Demo
Initialize
s B C D E
d0(u) 0 ∞ ∞ ∞ ∞
𝑋 = { }
s
B D
C E
10
3
1 4 7 98
2
2
0

 

Dijkstra’s Algorithm: Demo
s B C D E
d0(u) 0 ∞ ∞ ∞ ∞
s
B D
C E
10
3
1 4 7 98
2
2
0
10
3 

Explore s
𝑋 = { 𝑠 }
Dijkstra’s Algorithm: Demo
s B C D E
d0(u) 0 ∞ ∞ ∞ ∞
d1(u) 0 10 3 ∞ ∞
s
B D
C E
10
3
1 4 7 98
2
2
0
10
3 

Explore s
𝑋 = { 𝑠 }
Dijkstra’s Algorithm: Demo
s B C D E
d0(u) 0 ∞ ∞ ∞ ∞
d1(u) 0 10 3 ∞ ∞
d2(u) 0 7 3 11 5
s
B D
C E
10
3
1 4 7 98
2
2
0
7
3 5
11
Explore C
𝑋 = {𝑠, 𝐶 }
Dijkstra’s Algorithm: Demo
s B C D E
d0(u) 0 ∞ ∞ ∞ ∞
d1(u) 0 10 3 ∞ ∞
d2(u) 0 7 3 11 5
d3(u) 0 7 3 11 5
s
B D
C E
10
3
1 4 7 98
2
2
0
7
3 5
11
Explore E
𝑋 = {𝑠, 𝐶, 𝐸 }
Dijkstra’s Algorithm: Demo
s B C D E
d0(u) 0 ∞ ∞ ∞ ∞
d1(u) 0 10 3 ∞ ∞
d2(u) 0 7 3 11 5
d3(u) 0 7 3 11 5
d4(u) 0 7 3 9 5
s
B D
C E
10
3
1 4 7 98
2
2
0
7
3 5
9
Explore B
𝑋 = {𝑠, 𝐶, 𝐸, 𝐵 }
Dijkstra’s Algorithm: Demo
s B C D E
d0(u) 0 ∞ ∞ ∞ ∞
d1(u) 0 10 3 ∞ ∞
d2(u) 0 7 3 11 5
d3(u) 0 7 3 11 5
d4(u) 0 7 3 9 5
𝑋 = {𝑠, 𝐶, 𝐸, 𝐵, 𝐷}
s
B D
C E
10
3
1 4 7 98
2
2
0
7
3 5
9
Don’t need to
explore D
Dijkstra’s Algorithm: Demo
s
B D
C E
10
3
1 4 7 98
2
2
0
7
3 5
9
Maintain parent
pointers so we
can find the
shortest paths
s B C D E
d0(u) 0 ∞ ∞ ∞ ∞
d1(u) 0 10 3 ∞ ∞
d2(u) 0 7 3 11 5
d3(u) 0 7 3 11 5
d4(u) 0 7 3 9 5
Implementing Dijkstra (Naively)
Dijkstra(G = (V,E,{w(e)},s):
d[s] ← 0, d[u] ← ∞ for every u != s
parent[u] ←⊥ for every u
Q ← V // Q holds the unexplored nodes
While (Q is not empty):
𝑢 ← argmin
𝑤∈𝑄
𝑑 𝑤 //Find closest unexplored
Remove 𝑢 from Q
// Update the neighbors of u
For (v in out[u]):
If (d[v] > d[u] + w(u,v)):
d[v] ← d[u] + w(u,v)
parent[v] ← u
Return (d, parent)
Correctness of Dijkstra
• Warmup 0: initially, 𝑑0 𝑠 is
the correct distance 𝑑(𝑠, 𝑠)
• Warmup 1: before we explore the second node 𝑣,
𝑑1(𝑣) is the correct distance 𝑑(𝑠, 𝑣)
s B C D E
d0(u) 0 ∞ ∞ ∞ ∞
d1(u) 0 10 3 ∞ ∞
d2(u) 0 7 3 11 5
d3(u) 0 7 3 11 5
d4(u) 0 7 3 9 5
Correctness of Dijkstra
• Invariant: before we explore the 𝑘-th node v,
𝑑𝑘−1(𝑣) is the correct distance
• 𝑑𝑘−1(𝑣): upper bound on distance from 𝑠 to 𝑣 before
exploring 𝑘-th node/after exploring (𝑘 − 1)-st node
• We just argued the invariant holds before we’ve
explored the 1st and 2nd nodes
Correctness of Dijkstra
𝑿
𝑠
𝑧
𝑣
𝑦
𝑷
𝑢
𝑷′
• Invariant: before we explore
the 𝑘-th node v, 𝑑𝑘−1(𝑣) is
correct
• Proof:
Correctness of Dijkstra
𝑿
𝑠
𝑧
𝑣
𝑦
𝑷
𝑢
𝑷′
• Invariant: before we explore
the 𝑘-th node v, 𝑑𝑘−1(𝑣) is
correct
• Proof:
CS3000: Algorithms & Data
Unit 4: Shortest Paths (in Weighted Graphs)
a. Dijkstra’s Algorithm
b. Priority Queues and Heaps
Priority Queues
• Need a data structure Q to hold key-value pairs so
that we can quickly find closest unexplored node
• Keys =
• Values =
• Need to support the following operations
• Insert(Q,k,v): add a new key-value pair
• Lookup(Q,k): return the value of some key
• ExtractMin(Q): identify the key with the smallest value
• DecreaseKey(Q,k,v): reduce the value of some key
Priority Queues
• Naïve approach: use a “dictionary”
• Insert, DecreaseKey, Lookup take O(1) time
• ExtractMin takes O(n) time
• Heaps: implement all operations in
O(log n) time where n is the number of keys
Heaps
• Organize key-value pairs as a complete binary tree
• Later we’ll see how to store pairs in an ordinary array
• Heap Order:
• If a is the parent of b, then value(a) ≤ value(b)
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
Each node represents a
key-value pair
Implementing ExtractMin
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
Where is the min?
Implementing ExtractMin
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
• If we delete the min, we get two binary trees
• We need to get back to having one tree
Implementing ExtractMin
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8)
(g,10) (z,3) (q,7) (p,11)
(x,16)
• Problem?
Implementing ExtractMin
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8)
(g,10) (z,3) (q,7) (p,11)
(x,16)
Fails to be a heap in one place
(x,16) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8)
(g,10) (z,3) (q,7) (p,11)
(c,2)
• # of levels:
Implementing ExtractMin
(x,16) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8)
(g,10) (z,3) (q,7) (p,11)
(c,2)
(z,3) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8)
(g,10) (x,16) (q,7) (p,11)
(c,2)
Implementing ExtractMin
(z,3) (f,5)
(h,15) (r,17) (o,20) (x,16) (b,15) (y,8)
(g,10) (e,9) (q,7) (p,11)
(c,2)
(z,3) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8)
(g,10) (x,16) (q,7) (p,11)
(c,2)
Implementing ExtractMin
• Three steps:
• Pull the minimum from the root
• Move the last element up to the root
• Repair the heap-order (“heapify down”)
(z,3) (f,5)
(h,15) (r,17) (o,20) (x,16) (b,15) (y,8)
(g,10) (e,9) (q,7) (p,11)
(c,2)(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
Implementing DecreaseKey
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,6) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
Fails to be
a heap
Implementing DecreaseKey
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (q,7) (y,8) (x,16)
(g,10) (z,3) (b,6) (p,11)
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,6) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
Fails to be
a heap
Implementing DecreaseKey
• Two steps:
• Change the key
• Repair the heap-order (“heapify up”)
Fails to be
a heap
Implementing Insert
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
(w,4)
Implementing Insert
Fails to be
a heap
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (w,4)
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
(w,4)(p,11)
Implementing Insert
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (w,4)
(a,1)
(c,2) (w,4)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (f,5)
(p,11)(p,11)
Implementing Insert
• Two steps:
• Put the new key in the last location
• Repair the heap-order (“heapify up”)
Implementation Using Arrays
• Maintain an array 𝑉 holding the values
• Maintain a dictionary 𝐾 mapping keys to values
• Can find the value (lookup) for a given key in 𝑂 1 time
Array V
(a,1)
(c,2) (f,5)
(h,15) (r,17) (o,20) (e,9) (b,15) (y,8) (x,16)
(g,10) (z,3) (q,7) (p,11)
Implementation Using Arrays
• Maintain an array 𝑉 holding the values
• Maintain a dictionary 𝐾 mapping keys to values
• Can find the value for a given key in 𝑂 1 time
• For any node i in the binary tree
• LeftChild(i) = 2i
• RightChild(i) = 2i+1
• Parent(i) = ⌊i/2⌋
Array V
Priority Queues via Heaps
• Heapify:
• O(1) time to fix a single triple
• With n keys, might have to fix O(log n) triples
• Total time to heapify is O(log n)
• Lookup takes O(1) time
• ExtractMin takes O(log n) time
• DecreaseKey takes O(log n) time
• Insert takes O(log n) time
CS3000: Algorithms & Data
Unit 4: Shortest Paths (in Weighted Graphs)
a. Dijkstra’s Algorithm
b. Priority Queues and Heaps
c. Implementing Dijkstra with Heaps
Implementing Dijkstra with Heaps
Dijkstra(G = (V,E,{ℓ(e)}, s):
Let Q be a new heap
Let parent[u] ← ⊥ for every u
Insert(Q,s,0), Insert(Q,u, ∞) for every u != s
While (Q is not empty):
(u,d[u]) ← ExtractMin(Q)
For (v in out[u]):
d[v] ← Lookup(Q,v)
If (d[v] > d[u] + ℓ(u,v)):
DecreaseKey(Q,v,d[u] + ℓ(u,v))
parent[v] ← u
Return (d, parent)
Dijkstra Summary:
• Dijkstra’s Algorithm solves single-source shortest paths
in non-negatively weighted graphs
• Algorithm can fail if edge weights are negative!
• Implementation:
• A priority queue supports all necessary operations
• Implement priority queues using binary heaps
• Overall running time of Dijkstra: 𝑂 𝑚 log 𝑛
• Can do even better using Fibonacci heaps!