Last week recap
• Dynamic Programming:
Ø Edit Distance
Ø Chain Matrix Multiplication Ø 0-1 Knapsack Problem
2021-02-08 CSC373 Winter 2021 – Sam Toueg 1
Dynamic Programing
Bellman-Ford’s Single-Source Shortest Paths
Algorithm
2021-02-08 CSC373 Winter 2021 – Sam Toueg 2
Single-Source Shortest Path
• Problem
ØInput:
• Each edge 𝑢, 𝑣 has a weight (“length’’) 𝑤!”
• Directed graph 𝐺 = 𝑉, 𝐸 Ø𝑤!”=∞if 𝑢,𝑣 ∉𝐸
• Source node 𝑠 ∈ 𝑉
ØOutput: length of a shortest path from 𝑠 to every node 𝑡 ∈ 𝑉
𝑠2𝑣 lengthoftheshortestpathfrom𝑠to𝑢=7 (path𝑠→𝑣→𝑢)
5 10
𝑢
2021-02-08
CSC373 Winter 2021 – Sam Toueg 3
Single-Source Shortest Path
• Problem
ØInput:
• Each edge 𝑢, 𝑣 has a weight (“length’’) 𝑤!”
• Directed graph 𝐺 = 𝑉, 𝐸 Ø𝑤!”=∞if 𝑢,𝑣 ∉𝐸
• •
• Source node 𝑠 ∈ 𝑉
ØOutput: length of a shortest path from 𝑠 to every node 𝑡 ∈ 𝑉
When the edge weights are non-negative Ø Dijkstra’s algorithm solves this problem
When the edge weights may be negative
Ø Dijkstra’s algorithm fails (we already saw why!) Ø How do we solve this problem in this case?
2021-02-08 CSC373 Winter 2021 – Sam Toueg 4
Single-Source Shortest Path
• Problem
ØInput:
• Each edge 𝑢, 𝑣 has a weight (“length’’) 𝑤!”
• Directed graph 𝐺 = 𝑉, 𝐸 with no negative cycle Ø𝑤!”=∞if 𝑢,𝑣 ∉𝐸
•
• Source node 𝑠 ∈ 𝑉
ØOutput: length of a shortest path from 𝑠 to every node 𝑡 ∈ 𝑉
Note: If 𝐺 has a negative-length cycle, the problem is not well defined!
Ø You can traverse the cycle arbitrarily many times to get arbitrarily “short” paths
3
𝑆 -2 D
S ⤳ D: length of the shortest path = −∞ S→B→C→S→B→C→S→⋯→B→C→D
B
-2
1 −1 −1 C
2021-02-08
CSC373 Winter 2021 – Sam Toueg 5
Single-Source Shortest Path
• Problem
ØInput:
• Each edge 𝑢, 𝑣 has a weight (“length’’) 𝑤!”
• Directed graph 𝐺 = 𝑉, 𝐸 with no negative cycle Ø𝑤!”=∞if 𝑢,𝑣 ∉𝐸
• Source node 𝑠 ∈ 𝑉
ØOutput: length of a shortest path from 𝑠 to every node 𝑡 ∈ 𝑉
Claim 1: With no negative cycles, for every node 𝑡 ∈ 𝑉, there is a shortest 𝑠 ⤳ 𝑡 path that is simple (i.e., that contains no repeated nodes)
Ø Consider a shortest 𝑠 ⤳ 𝑡 path
Ø If it has a repeated node, it contains a cycle, remove the cycle;
this path has fewer repeated nodes and is not longer than the original path Ø Repeat this until the 𝑠 ⤳ 𝑡 path is simple
Corollary 1: With no negative cycles, for every node 𝑡 ∈ 𝑉, there is a shortest 𝑠 ⤳ 𝑡 path
with at most 𝑛 − 1 edges
2021-02-08 CSC373 Winter 2021 – Sam Toueg 6
Single-Source Shortest Path
• Consider a shortest 𝑠 ⤳ 𝑡 path 𝑃
• Consider the node 𝑢 that immediately precedes 𝑡 in 𝑃
𝑃:
shortest 𝑠 ⤳ 𝑡
𝑠 𝑢𝑤𝑡
!$ 𝑃′: shortest𝑠⤳𝑢
• Two possible cases:
Øthispathusesatmost𝑖−1edges: 𝑂𝑃𝑇 𝑖,𝑡 =𝑂𝑃𝑇(𝑖−1,𝑡)
o𝑃# =𝑃 −(𝑢,𝑡)mustbeashortest𝑠⤳𝑢path
• 𝑂𝑃𝑇(𝑖, 𝑡) = length of a shortest 𝑠 ⤳ 𝑡 path using at most 𝑖 edges
Øthispathusesexactly𝑖edges: • Bellman equation:
0
𝑂𝑃𝑇𝑖,𝑡 = ∞
min 𝑂𝑃𝑇 𝑖−1,𝑡 ,min{𝑂𝑃𝑇 𝑖−1,𝑢 +𝑤!$} !∈#
𝑂𝑃𝑇 𝑛−1,𝑡 =lengthofshortestpathto𝑡
𝑂𝑃𝑇 𝑖,𝑡 =min{𝑂𝑃𝑇 𝑖−1,𝑢 +𝑤!$} !∈#
if 𝑖 = 0 ∧ 𝑡 = 𝑠 if𝑖=0∧𝑡≠𝑠
if𝑖>0
2021-02-08 CSC373 Winter 2021 – Sam Toueg
7
Single-Source Shortest Path
• Bellman equation:
0
𝑂𝑃𝑇𝑖,𝑡 = ∞
min 𝑂𝑃𝑇 𝑖−1,𝑡 ,min{𝑂𝑃𝑇 𝑖−1,𝑢 +𝑤!$} !∈#
• Bellman-Ford Algorithm: 𝑂𝑃𝑇(0, 𝑠) ← 0
for all nodes 𝑡 ≠ 𝑠 do
𝑂𝑃𝑇(0, 𝑡) ← ∞ for all 𝑖 = 1 to 𝑛 − 1 do
if 𝑖 = 0 ∧ 𝑡 = 𝑠 if𝑖=0∧𝑡≠𝑠
if𝑖>0
for all node 𝑡 do
𝑂𝑃𝑇(𝑖,𝑡) ← min 𝑂𝑃𝑇 𝑖 − 1,𝑡 ,min{𝑂𝑃𝑇 𝑖 − 1,𝑢 + 𝑤!&}
Time complexity?
!∈%
2021-02-08 CSC373 Winter 2021 – Sam Toueg 8
Single-Source Shortest Path
• Bellman-Ford Algorithm: 𝑂𝑃𝑇(0, 𝑠) ← 0
for all nodes 𝑡 ≠ 𝑠 do 𝑂𝑃𝑇(0, 𝑡) ← ∞
𝑂(𝑛) forall𝑖=1to𝑛−1do
adjacency matrix:
𝑂(𝑛%)
for all node 𝑡 do
𝑂𝑃𝑇(𝑖,𝑡) ← min 𝑂𝑃𝑇 𝑖 − 1,𝑡 ,min{𝑂𝑃𝑇 𝑖 − 1,𝑢 + 𝑤!&}
!∈%
Time complexity?
adjacency matrix:
𝑂(𝑛&)
2021-02-08 CSC373 Winter 2021 – Sam Toueg 9
Single-Source Shortest Path
• Bellman-Ford Algorithm: 𝑂𝑃𝑇(0, 𝑠) ← 0
for all nodes 𝑡 ≠ 𝑠 do 𝑂𝑃𝑇(0, 𝑡) ← ∞
𝑂(𝑛) forall𝑖=1to𝑛−1do
(reverse) adjacency list:
𝑂(𝑚)
for all node 𝑡 do
𝑂𝑃𝑇(𝑖,𝑡)←min 𝑂𝑃𝑇 𝑖−1,𝑡 , min {𝑂𝑃𝑇 𝑖−1,𝑢 +𝑤!&}
(!,&)∈*
Time complexity?
adjacency list:
𝑂(𝑛 X 𝑚)
2021-02-08
CSC373 Winter 2021 – Sam Toueg
10
Single-Source Shortest Path
• Bellman-Ford Algorithm: 𝑂𝑃𝑇(0, 𝑠) ← 0
for all nodes 𝑡 ≠ 𝑠 do 𝑂𝑃𝑇(0, 𝑡) ← ∞
𝑂(𝑛) forall𝑖=1to𝑛−1do
for all node 𝑡 do
𝑂𝑃𝑇(𝑖,𝑡)←min 𝑂𝑃𝑇 𝑖−1,𝑡 , min {𝑂𝑃𝑇 𝑖−1,𝑢 +𝑤!&} (!,&)∈*
Time complexity?
adjacency matrix
𝑂(𝑛!)
adjacency list
𝑂(𝑛%𝑚)
2021-02-08
CSC373 Winter 2021 – Sam Toueg 11
Single-Source Shortest Path
• Bellman-Ford Algorithm: 𝑂𝑃𝑇(0, 𝑠) ← 0
for all nodes 𝑡 ≠ 𝑠 do 𝑂𝑃𝑇(0, 𝑡) ← ∞
for all 𝑖 = 1 to 𝑛 − 1 do for all node 𝑡 do
𝑂𝑃𝑇(𝑖,𝑡) ← min 𝑂𝑃𝑇 𝑖 − 1,𝑡 ,min{𝑂𝑃𝑇 𝑖 − 1,𝑢 + 𝑤!&} !∈%
Spacecomplexity? 𝑂𝑃𝑇 𝑖,𝑡 for𝑖=1to𝑛−1,andallnodes𝑡∈𝑉 𝜃(𝑛%) Better space complexity?
To compute 𝑂𝑃𝑇 𝑖,∗ we only need 𝑂𝑃𝑇 𝑖 − 1,∗ ⟹needtokeeponlytworows𝑂𝑃𝑇 𝑖−1,∗ and𝑂𝑃𝑇 𝑖,∗ atatime 𝜃(𝑛)
2021-02-08 CSC373 Winter 2021 – Sam Toueg 13
Single-Source Shortest Path
• Bellman-Ford Algorithm: 𝑂𝑃𝑇(0, 𝑠) ← 0
for all nodes 𝑡 ≠ 𝑠 do 𝑂𝑃𝑇(0, 𝑡) ← ∞
for all 𝑖 = 1 to 𝑛 − 1 do for all node 𝑡 do
𝑂𝑃𝑇(𝑖,𝑡) ← min 𝑂𝑃𝑇 𝑖 − 1,𝑡 ,min{𝑂𝑃𝑇 𝑖 − 1,𝑢 + 𝑤!&} !∈%
How to find the actual shortest path?
For each node 𝑡:
keep track of the current predecessor of 𝑡 in the shortest path 𝑠 ⤳ 𝑡
Initially: 𝑝[𝑡] ← NIL
Update 𝑝[𝑡] each time a shorter path to 𝑡 is discovered
2021-02-08 CSC373 Winter 2021 – Sam Toueg 14
Detecting Negative Cycles
𝑂𝑃𝑇(𝑖,𝑡) ← min 𝑂𝑃𝑇 𝑖 − 1,𝑡 ,min{𝑂𝑃𝑇 𝑖 − 1,𝑢 + 𝑤!&}
• Claim 2:
!∈%
∀𝑡,𝑂𝑃𝑇 𝑘,𝑡 =𝑂𝑃𝑇 𝑘−1,𝑡 ⟹ ∀𝑡,𝑂𝑃𝑇 𝑘+1,𝑡 =𝑂𝑃𝑇 𝑘,𝑡
• Proof:
• Corollary 2:
𝑂𝑃𝑇 𝑘+1,𝑡 =min 𝑂𝑃𝑇 𝑘,𝑡 ,min{𝑂𝑃𝑇 𝑘,𝑢 +𝑤!$} !∈#
=min 𝑂𝑃𝑇 𝑘−1,𝑡 ,min{𝑂𝑃𝑇 𝑘−1,𝑢 +𝑤!$} !∈#
=𝑂𝑃𝑇 𝑘,𝑡
∀𝑡,𝑂𝑃𝑇 𝑛,𝑡 =𝑂𝑃𝑇 𝑛−1,𝑡 ⟹∀𝑡,∀𝑛# ≥𝑛,𝑂𝑃𝑇 𝑛′,𝑡 =𝑂𝑃𝑇 𝑛−1,𝑡
2021-02-08 CSC373 Winter 2021 – Sam Toueg 15
Detecting Negative Cycles
Recall: 𝑂𝑃𝑇(𝑘, 𝑡) = length of a shortest 𝑠 ⤳ 𝑡 path using at most k edges
• Corollary 2:
∀𝑡,𝑂𝑃𝑇 𝑛,𝑡 =𝑂𝑃𝑇 𝑛−1,𝑡 ⟹ ∀𝑡,∀𝑛# ≥𝑛,𝑂𝑃𝑇 𝑛′,𝑡 =𝑂𝑃𝑇 𝑛−1,𝑡
𝐺 has no negative
lengthcycle ⟺ ∀𝑡∈𝑉,𝑂𝑃𝑇 𝑛,𝑡 =𝑂𝑃𝑇 𝑛−1,𝑡 reachable from 𝑠
• Proof:
• ⇒ Immediate from Corollary 1 (∀𝑡 there is a shortest 𝑠 ⤳ 𝑡 path with 𝑛 − 1 egdes)
•⇐Suppose∀𝑡∈𝑉,𝑂𝑃𝑇 𝑛,𝑡 =𝑂𝑃𝑇 𝑛−1,𝑡
ØBy Corollary 2, ∀𝑡,∀𝑛# ≥ 𝑛,𝑂𝑃𝑇 𝑛′,𝑡 = 𝑂𝑃𝑇 𝑛 − 1,𝑡 (*)
ØSuppose, for contradiction, that 𝐺 has a negative cycle reachable from 𝑠.
Then we can find an 𝑠 ⤳ 𝑡 path to some node 𝑡 in this cycle, and we can make the length of 𝑠 ⤳ 𝑡 smaller and smaller by repeating this negative cycle
(i.e., adding the cycle edges to the 𝑠 ⤳ 𝑡 path) — contradicting (*)
Ø So 𝐺 has no negative length cycle reachable from 𝑠
2021-02-08 CSC373 Winter 2021 – Sam Toueg 17
• Claim 3:
Detecting Negative Cycles
𝐺 has no negative
•Claim3: lengthcycle ⟺ ∀𝑡∈𝑉,𝑂𝑃𝑇 𝑛,𝑡 =𝑂𝑃𝑇 𝑛,𝑡−1
reachable from 𝑠
Claim 3 gives a way to detect whether 𝐺 has a negative cycle reachable from 𝑠: • Run Bellman-Ford algorithm for 1, 2, … , 𝑛 − 1, 𝑛, that is for 𝑛 iterations
• If∀𝑡,𝑂𝑃𝑇 𝑛,𝑡 =𝑂𝑃𝑇 𝑛−1,𝑡 ,thennonegativecyclereachablefrom𝑠 • If∃𝑡,𝑂𝑃𝑇 𝑛,𝑡 ≠𝑂𝑃𝑇 𝑛−1,𝑡 ,then∃anegativecyclereachablefrom𝑠
How to detect whether 𝐺 has a negative cycle that may not be reachable from 𝑠?
detect negative cycles reachable from 𝑠̂ by running B-F on 𝐺b
𝑠̂
0
0 0
𝐺b
0
𝑠⋯ 𝐺
2021-02-08 CSC373 Winter 2021 – Sam Toueg 18
Finding a Negative Cycle
• Claim4:Supposethat𝑂𝑃𝑇 𝑛,𝑢 ≠𝑂𝑃𝑇 𝑛−1,𝑢 forsome𝑢 Let𝑃bean𝑠⤳𝑢pathoflength𝑂𝑃𝑇 𝑛,𝑢 andwithatmost𝑛edges (1) 𝑃 contains a cycle
(2) Every cycle on 𝑃 has negative length
• Proof:Since𝑂𝑃𝑇 𝑛,𝑢 ≠𝑂𝑃𝑇 𝑛−1,𝑢 ,clearly (*) Let𝑃= 𝑠 𝑃 𝑣 𝑃 𝑣 𝑃 𝑢
(%& withlength𝑂𝑃𝑇 𝑛,𝑢 andatmost𝑛edges. Since𝑂𝑃𝑇 𝑛,𝑢 <𝑂𝑃𝑇 𝑛−1,𝑢 :
⇒ 𝑃 has exactly 𝑛 edges and 𝑛 + 1 nodes ⇒ some node 𝑣 repeats
⇒ (1) holds because 𝑃% is a 𝑣 to 𝑣 cycle
We claim that cycle 𝑃% has negative length, and so (2) also holds. Suppose, for contradiction, that cycle 𝑃% has length ≥ 0. ' Then remove 𝑃% from path 𝑃 to get the following 𝑠 ⤳ 𝑢 path 𝑃 :
𝑂𝑃𝑇 𝑛,𝑢 <𝑂𝑃𝑇 𝑛−1,𝑢
𝑃'=𝑠 𝑃 𝑣 𝑃 𝑢 ('&'
Clearly:(a)lengthof𝑃≥lengthof𝑃 and(b)𝑃 hasatmost𝑛−1edges
So: --- a contradiction to (*)
𝑂𝑃𝑇 𝑛,𝑢 ≥lengthof𝑃'≥𝑂𝑃𝑇 𝑛−1,𝑢