程序代写代做代考 Bioinformatics DNA C algorithm data structure assembly graph 6. DYNAMIC PROGRAMMING II

6. DYNAMIC PROGRAMMING II
‣ sequence alignment
‣ Hirschberg′s algorithm
‣ Bellman–Ford–Moore algorithm ‣ distance-vector protocols
‣ negative cycles
Lecture slides by Kevin Wayne
 Copyright © 2005 Pearson-Addison Wesley

http://www.cs.princeton.edu/~wayne/kleinberg-tardos
Last updated on 4/8/18 7:52 PM

6. DYNAMIC PROGRAMMING II
‣ sequence alignment
‣ Hirschberg′s algorithm
‣ Bellman–Ford–Moore algorithm ‣ distance-vector protocols
‣ negative cycles
SECTION 6.6

String similarity
Q. How similar are two strings? 

Ex. ocurrance and occurrence.
o
c
u
r
r
a
n
c
e

o
c

u
r
r
a
n
c
e
o
c
c
u
r
r
e
n
c
e
o
c
c
u
r
r
e
n
c
e
6 mismatches, 1 gap
1 mismatch, 1 gap
o
c

u
r
r

a
n
c
e
o
c
c
u
r
r
e

n
c
e
0 mismatches, 3 gaps
3

Edit distance
Edit distance. [Levenshtein 1966, Needleman–Wunsch 1970] 􏰞Gap penalty δ; mismatch penalty αpq.
􏰞Cost = sum of gap and mismatch penalties.

 
 
 
 
 
 
 

cost=δ+αCG +αTA
C
T

G
A
C
C
T
A
C
G
C
T
G
G
A
C
G
A
A
C
G
Applications. Bioinformatics, spell correction, machine translation,
 speech recognition, information extraction, …
assumingαAA=αCC=αGG=αTT =0
Spokesperson confirms senior government adviser was found 

Spokesperson said the senior adviser was found
4

BLOSUM matrix for proteins
5

Dynamic programming: quiz 1
What is edit distance between these two strings?


 

PALETTE PALATE
Assume gap penalty = 2 and mismatch penalty = 1. 

A. 1 B. 2 C. 3 D. 4 E. 5
P
A
L
E
T
T
E
P
A
L
A

T
E
1 mismatch, 1 gap
6


mismatch gap
x1 x2 x3 x4 x5 x6
Sequence alignment
Goal. Given two strings x1 x2 … xm and y1 y2 … yn , find a min-cost alignment. 

Def. An alignment M is a set of ordered pairs xi – yj such that each character appears in at most one pair and no crossings.

xi – yj and xiʹ – yj′ cross if i < i ′, but j > j ʹ cost(M)=∑αxiyj+ ∑δ+∑δ
Def. The cost of an alignment M is:
(x ,y )∈M i:x unmatched j:y unmatched
!##”##$ !####”#####$
ijij
C
T
A
C
C

G

T
A
C
A
T
G
y1 y2 y3 y4 y5 y6
an alignment of CTACCG and TACATG
M = { x2–y1, x3–y2, x4–y3, x5–y4, x6–y6 }
7

Sequence alignment: problem structure
Def. OPT(i, j) = min cost of aligning prefix strings x1 x2 … xi and y1 y2 … yj. Goal. OPT(m,n).

Case 1. OPT(i, j) matches xi – yj.
Pay mismatch for xi – yj + min cost of aligning x1 x2 … xi–1 and y1 y2 … yj–1. 

Case 2a. OPT(i, j) leaves xi unmatched.
Pay gap for xi + min cost of aligning x1 x2 … xi–1 and y1 y2 … yj.

optimal substructure property (proof via exchange argument)
􏰎 􏰏 i = 0
Case 2b. OPT(i, j) leaves yj unmatched.
Pay gap for yj + min cost of aligning x1 x2 … xi and y1 y2 … yj–1.

Bellman equation.
OPT(i,j) =
j
i
xiyj
min + OPT(i1,j)
+ OPT(i,j1)
􏰎􏰏 j = 0 + OPT(i1,j1)
􏰑􏰗􏰚􏰌􏰖􏰛􏰎􏰍􏰌
8

Sequence alignment: bottom-up algorithm
SEQUENCE-ALIGNMENT(m, n, x1, …, xm, y1, …, yn, δ, α) ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ FOR i = 0 TO m
M[i, 0] ← iδ. FOR j = 0 TO n
M[0, j] ← jδ.

FOR i = 1 TO m FOR j = 1 TO n
M[i, j] ← min { αxi yj + M[i–1, j–1], δ + M[i–1, j],
δ + M [i, j – 1] }.

RETURN M [m, n]. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
already computed
9

Sequence alignment: traceback
SIMILARITY
0
2
4
6
8
10
12
14
16
18
20
2
4
1
3
2
4
6
8
7
9
11
4
6
3
3
4
4
6
8
9
9
11
6
8
5
5
6
6
6
8
10
11
11
8
10
7
7
8
8
8
8
10
12
13
10
12
9
9
9
10
10
10
10
9
11
12
14
8
10
8
10
12
12
9
11
11
14
16
10
10
10
10
12
14
11
8
11
16
18
12
12
12
12
12
14
13
10
7
I D E N T I T Y
10

Sequence alignment: analysis
Theorem. The DP algorithm computes the edit distance (and an optimal alignment) of two strings of lengths m and n in Θ(mn) time and space. Pf.
􏰞Algorithm computes edit distance.
􏰞Can trace back to extract optimal alignment itself. ▪ 


 

Theorem. [Backurs–Indyk 2015] If can compute edit distance of two strings
 of length n in O(n2−ε) time for some constant ε > 0, then can solve SAT

with n variables and m clauses in poly(m) 2(1−δ) n time for some constant δ > 0.
which would disprove SETH (strong exponential time hypothesis)
Edit Distance Cannot Be Computed in Strongly Subquadratic Time
(unless SETH is false)∗
Arturs Backurs† Piotr Indyk‡ MIT MIT
Abstract
11
5 Aug 2017

Dynamic programming: quiz 3
It is easy to modify the DP algorithm for edit distance to…
A. Compute edit distance in O(mn) time and O(m + n) space.
B. Compute an optimal alignment in O(mn) time and O(m + n) space.
C. Both A and B.
D. Neither A nor B.
j
i
OPT(i,j) = xiyj
min + OPT(i1,j)
+ OPT(i,j1)
􏰎 􏰏 i = 0
􏰎 􏰏 j = 0 + OPT(i1,j1)
􏰑􏰗􏰚􏰌􏰖􏰛􏰎􏰍􏰌
12

6. DYNAMIC PROGRAMMING II
‣ sequence alignment
‣ Hirschberg′s algorithm
‣ Bellman–Ford–Moore algorithm ‣ distance-vector protocols
‣ negative cycles
SECTION 6.7

Sequence alignment in linear space
Theorem. [Hirschberg] There exists an algorithm to find an optimal alignment in O(mn) time and O(m + n) space.
􏰞􏰞Clever combination of divide-and-conquer and dynamic programming. Inspired by idea of Savitch from complexity theory.
Programming Techniques
G. Manacher Editor
A = axa2…am if and only if there is a mapping F: {1, 2, …, p} ~ {1, 2, …, m} such thatf(i) = k only if c~ is ak and F is a monotone strictly increasing func- tion(i.e.F(i) = u,F(j) = v,andi__ t. When k > t, we shall write ]3kt so as to make clear that we are referring to a “reverse substring” of D.
L(i, j) is the maximum length possible of any com- mon subsequence of Ax~and B~s.
x[ lY is the concatenation of strings x and y.
We present the algorithm described in [3], which takes quadratic time and space.
Algorithm A
Algorithm A accepts as input strings A~m and Bx. and produces as output the matrix L (where the ele- ment L(i, j) corresponds to our notation of maximum length possible of any common subsequence of Axl and B.).
ALGA (m,n,A,B,L)
1. Initialization: L(i, 0) ~ 0 [i=0…m];
A Linear Space Algorithm for Computing Maximal Common Subsequences D.S. Hirschberg
Princeton University
The problem of finding a longest common subse- quence of two strings has been solved in quadratic time and space. An algorithm is presented which will solve this problem in quadratic time and in linear space.
Key Words and Phrases: subsequence, longest common subsequence, string correction, editing
CR Categories: 3.63, 3.73, 3.79, 4.22, 5.25
Introduction
14
The problem of finding a longest common subse-
L(O,j) +–0 [j=0…n];
2. for i +– 1 to m do

Hirschberg′s algorithm
Edit distance graph.
􏰞􏰞Let f (i, j) denote length of shortest path from (0,0) to (i, j). Lemma: f (i, j) = OPT(i, j) for all i and j.
ε y1 y2 y3 y4 y5 y6 0–0
ε
x1
x2
αxiyj
δ i–j
δ

x3
m–n
15

Hirschberg′s algorithm
Edit distance graph.
􏰞Let f (i, j) denote length of shortest path from (0,0) to (i, j). 􏰞Lemma: f (i, j) = OPT(i, j) for all i and j.
Pf of Lemma. [ by strong induction on i + j ]
􏰞Base case: f(0, 0) = OPT(0, 0) = 0.
􏰞Inductive hypothesis: assume true for all (iʹ, jʹ) with iʹ + jʹ < i + j. 􏰞Last edge on shortest path to (i, j) is from (i – 1, j – 1), (i – 1, j), or (i, j – 1). 􏰞Thus, f(i,j) = f(i,j) = min{ min{xi yj +f(i1,j1), +f(i1,j), +f(i,j1)} +f(i1,j1), +f(i1,j), +f(i,j1)} +OPT(i1,j1), +OPT(i1,j), +OPT(i,j1)} +OPT(i1,j1), +OPT(i1,j), +OPT(i,j1)} inductive hypothesis Bellman equation = min{ = min{xi yj xi yj = OPT(i,j) = OP T (i, j) ▪ xi yj αxi y j δ i–j €δ 16 Hirschberg’s algorithm Edit distance graph. 􏰞Let f (i, j) denote length of shortest path from (0,0) to (i, j). 􏰞Lemma: f (i, j) = OPT(i, j) for all i and j. 􏰞Can compute f (·, j) for any j in O(mn) time and O(m + n) space. ε y1 y2 y3 0–0 x1 x2 y5 y6 j y4 i–j ε x3 m–n 17 Hirschberg’s algorithm Edit distance graph. 􏰞Let g(i, j) denote length of shortest path from (i, j) to (m, n). ε y1 y2 y3 y4 y5 y6 ε x1 x2 0–0 i–j x3 m–n 18 Hirschberg’s algorithm Edit distance graph. 􏰞􏰞Let g(i, j) denote length of shortest path from (i, j) to (m, n). Can compute g(i, j) by reversing the edge orientations and
 inverting the roles of (0, 0) and (m, n). ε y1 y2 y3 y4 y5 y6 ε x1 x2 0–0 i–j δ xi+1yj+1 δ x3 m–n 19 Hirschberg’s algorithm Edit distance graph. 􏰞􏰞Let g(i, j) denote length of shortest path from (i, j) to (m, n). Can compute g(·, j) for any j in O(mn) time and O(m + n) space. ε y1 y2 0–0 x1 x2 y4 y5 y6 j y3 i–j ε x3 m–n 20 Hirschberg’s algorithm Observation 1. The length of a shortest path that uses (i, j) is f (i, j) + g(i, j). ε x1 x2 ε y1 y2 y3 y4 y5 y6 0–0 i–j x3 m–n 21 Hirschberg’s algorithm Observation 2. let q be an index that minimizes f (q, n / 2) + g (q, n / 2).
 Then, there exists a shortest path from (0, 0) to (m, n) that uses (q, n / 2). ε y1 y2 0–0 y4 y5 y6 n/2 y3 i–j ε x1 q x2 x3 m–n 22 Hirschberg’s algorithm Divide. Find index q that minimizes f (q, n / 2) + g(q, n / 2); save node i–j as part of solution. 
 Conquer. Recursively compute optimal alignment in each piece. n/2 ε x1 ε y1 y2 y3 0–0 i–j m–n y4 y5 y6 q x2 x3 23 Hirschberg’s algorithm: space analysis Theorem. Hirschberg’s algorithm uses Θ(m + n) space. 
 Pf. 􏰞Each recursive call uses Θ(m) space to compute f (·, n / 2) and g(·, n / 2). 􏰞Only Θ(1) space needs to be maintained per recursive call. 􏰞Number of recursive calls ≤ n. ▪ 24 Dynamic programming: quiz 4 What is the worst-case running time of Hirschberg’s algorithm?
 A. O(mn) B. O(mn log m) C. O(mn log n) D. O(mn log m log n) 25 Hirschberg’s algorithm: running time analysis warmup Theorem. Let T(m, n) = max running time of Hirschberg’s algorithm on strings of lengths at most m and n. Then, T(m, n) = O(m n log n). 
 Pf. 􏰞T(m, n) is monotone nondecreasing in both m and n. 􏰞T(m,n) ≤ 2T(m,n/2) + O(mn) 
 
 
 ⇒ T(m,n) = O(mnlogn). Remark. Analysis is not tight because two subproblems are of size
 (q, n/2) and (m – q, n/2). Next, we prove T(m, n) = O(m n). 26 Hirschberg′s algorithm: running time analysis Theorem. Let T(m, n) = max running time of Hirschberg’s algorithm on strings of lengths at most m and n. Then, T(m, n) = O(m n). 
 Pf. [ by strong induction on m + n ] 􏰞O(m n) time to compute f ( ·, n / 2) and g ( ·, n / 2) and find index q. 􏰞T(q, n/2) + T(m – q, n/2) time for two recursive calls. 􏰞Choose constant c so that:
 T(m, 2) ≤ c m 
 T(2,n) ≤ cn T(m, n) ≤ c m n + T(q, n / 2) + T(m – q, n / 2) 􏰞Claim. T(m, n) ≤ 2cmn. 􏰞Base cases: m = 2 and n = 2. 􏰞Inductive hypothesis: T(m, n) ≤ 2cmn for all (mʹ, nʹ) with mʹ + nʹ < m + n. ≤ T(q, n / 2) + T(m – q, n / 2) + c m n ≤ 2cqn/2 + 2c(m–q)n/2 + cmn = cqn + cmn – cqn + cmn =2cmn▪ T(m, n) inductive hypothesis 27 LONGEST COMMON SUBSEQUENCE Problem. Given two strings x1 x2 ... xm and y1 y2 ... yn , find a common subsequence that is as long as possible. 
 Alternative viewpoint. Delete some characters from x ; delete some character from y ; a common subsequence if it results in the same string. Ex. LCS(GGCACCACG, ACGGCGGATACG ) = GGCAACG. 
 Applications. Unix diff, git, bioinformatics. 28 6. DYNAMIC PROGRAMMING II ‣ sequence alignment ‣ Hirschberg′s algorithm ‣ Bellman–Ford–Moore algorithm ‣ distance-vector protocols ‣ negative cycles SECTION 6.8 Shortest paths with negative weights Shortest-path problem. Given a digraph G = (V, E), with arbitrary edge lengths 􏰟vw, find shortest path from source node s to destination node t. assume there exists a path from every node to t s 5 4 8 2 12 5 9 7 9 1 5 3 6 5 11 13 4 10 t length of shortest path from s to t = 9 − 3 − 6 + 11 = 11 32 Shortest paths with negative weights: failed attempts Dijkstra. May not produce shortest paths when edge lengths are negative. 
 
 
 
 
 
 
 
 s6v 8 Dijkstra selects the vertices in the order s, t, w, v But shortest path from s to t is s→v→w→t. 4 t3w 2 Reweighting. Adding a constant to every edge length does not necessarily make Dijkstra’s algorithm produce shortest paths. s 14 v 10 t 11 w Adding 8 to each edge weight changes the shortest path from s→v→w→t to s→t. 12 0 33 Negative cycles Def. A negative cycle is a directed cycle for which the sum of its edge lengths is negative. 5 3 3 4 4 (W) = e < 0 eW a negative cycle W : 34 Shortest paths and negative cycles Lemma 1. If some v↝t path contains a negative cycle, then there does not exist a shortest v↝t path. 
 Pf. If there exists such a cycle W, then can build a v↝t path of arbitrarily negative length by detouring around W as many times as desired. ▪ v t W 􏰟(W) < 0 35 Shortest paths and negative cycles Lemma 2. If G has no negative cycles, then there exists a shortest v↝t path that is simple (and has ≤ n – 1 edges). 
 Pf. 􏰞Among all shortest v↝t paths, consider one that uses the fewest edges. 􏰞If that path P contains a directed cycle W, can remove the portion of P corresponding to W without increasing its length. ▪ v t W 􏰟(W) ≥ 0 36 Shortest-paths and negative-cycle problems Single-destination shortest-paths problem. Given a digraph G = (V, E) with edge lengths 􏰟vw (but no negative cycles) and a distinguished node t,
 find a shortest v↝t path for every node v. 
 Negative-cycle problem. Given a digraph G = (V, E) with edge lengths 􏰟vw, find a negative cycle (if one exists). 1 42 3 5 5 3 3 t 4 4 negative cycle shortest-paths tree 37 Dynamic programming: quiz 5 Which subproblems to find shortest v↝t paths for every node v?
 A. OPT(i, v) = length of shortest v↝t path that uses exactly i edges. B. OPT(i, v) = length of shortest v↝t path that uses at most edges. C. Neither A nor B. 38 Shortest paths with negative weights: dynamic programming Def. OPT(i, v) = length of shortest v↝t path that uses ≤ i edges. 
 Goal. OPT(n – 1, v) for each v. 
 by Lemma 2, if no negative cycles, Case 1. Shortest v↝t path uses ≤ i – 1 edges. 􏰞OPT(i, v) = OPT(i – 1, v).
 there exists a shortest v↝t path that is simple optimal substructure property (proof via exchange argument) Case 2. Shortest v↝t path uses exactly i edges. 􏰞if (v, w) is first edge in shortest such v↝t path, incur a cost of 􏰟vw. 􏰞Then, select best w↝t path using ≤ i – 1 edges. 
 Bellman equation. OPT(i,v) = 0 􏰎 􏰏 i = 0 􏰕 􏰐 􏰒 v = t 􏰎􏰏i=0􏰕􏰐􏰒v=t min OPT(i1,v), min {OPT(i1,w)+vw} 􏰎􏰏i>0 (v,w)E
39

Shortest paths with negative weights: implementation
SHORTEST-PATHS(V, E, 􏰟, t) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
FOREACH node v ∈ V : M [0, v] ← ∞.
M [0, t] ← 0.
FOR i = 1 TO n – 1
FOREACH node v ∈ V :
M[i, v] ← M[i–1, v]. FOREACH edge (v, w) ∈ E :
M [i, v] ← min { M [i, v], _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
M [i – 1, w] + 􏰟vw }.
40

Shortest paths with negative weights: implementation
Theorem 1. Given a digraph G = (V, E) with no negative cycles, the DP algorithm computes the length of a shortest v↝t path for every node v
 in Θ(mn) time and Θ(n2) space.

Pf.
􏰞Table requires Θ(n2) space.
􏰞Each iteration i takes Θ(m) time since we examine each edge once. ▪ 

Finding the shortest paths.
􏰞Approach 1: Maintain successor[i, v] that points to next node
 on a shortest v↝t path using ≤ i edges.
􏰞Approach 2: Compute optimal lengths M[i, v] and consider
 only edges with M[i, v] = M[i – 1, w] + 􏰟vw. Any directed path in this subgraph is a shortest path.
41

Dynamic programming: quiz 6
It is easy to modify the DP algorithm for shortest paths to…
A. Compute lengths of shortest paths in O(mn) time and O(m + n) space.
B. Compute shortest paths in O(mn) time and O(m + n) space.
C. Both A and B.
D. Neither A nor B.
42

Shortest paths with negative weights: practical improvements
Space optimization. Maintain two 1D arrays (instead of 2D array). 􏰞d[v] = length of a shortest v↝t path that we have found so far. 􏰞successor[v] = next node on a v↝t path.

Performance optimization. If d[w] was not updated in iteration i – 1,
 then no reason to consider edges entering w in iteration i.
43

Bellman–Ford–Moore: efficient implementation
BELLMAN–FORD–MOORE(V, E, c, t) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
FOREACH node v ∈ V : d[v] ← ∞.
successor[v] ← null. d[t] ← 0.
FOR i = 1 TO n – 1 FOREACH node w ∈ V :
IF (d[w] was updated in previous pass) FOREACH edge (v, w) ∈ E :
IF (d[v] > d[w] + 􏰟vw)
d[v] ← d[w] + 􏰟vw.
successor[v] ← w.
pass i O(m) time
IF (no d[⋅] value changed in pass i) STOP. _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
44

Dynamic programming: quiz 7
Which properties must hold after pass i of Bellman–Ford–Moore?

A. d[v] = length of a shortest v↝t path using ≤ i edges.
B. d[v] = length of a shortest v↝t path using exactly i edges.
C. Both A and B.
D. Neither A nor B.
d[v] = 3 d[w] = 2 d[t] = 0 v1w2t
4
if node w considered before node v, then d[v] = 3 after 1 pass
45

Bellman–Ford–Moore: analysis
Lemma 3. For each node v : d[v] is the length of some v↝t path. Lemma 4. For each node v : d[v] is monotone non-increasing.

Lemma 5. After pass i, d[v] ≤ length of a shortest v↝t path using ≤ i edges. Pf. [ by induction on i ]
􏰞Base case: i = 0.
􏰞Assume true after pass i.
􏰞Let P be any v↝t path with ≤ i + 1 edges.
􏰞Let (v, w) be first edge in P and let Pʹ be subpath from w to t. 􏰞By inductive hypothesis, at the end of pass i, d[w] ≤ c(P ʹ)

because P ʹ is a w↝t path with ≤ i edges. 􏰞After considering edge (v, w) in pass i + 1:
d[v] ≤ 􏰟vw + d[w]
and by Lemma 4, d[w] does not increase
and by Lemma 4, d[v] does not increase

􏰟vw + c(Pʹ) = 􏰟(P) ▪
46

Bellman–Ford–Moore: analysis
Theorem 2. Assuming no negative cycles, Bellman–Ford–Moore computes the lengths of the shortest v↝t paths in O(mn) time and Θ(n) extra space. Pf. Lemma 2 + Lemma 5. ▪


shortest path exists and has at most n−1 edges
after i passes,
d[v] ≤ length of shortest path
that uses ≤ i edges

 
 

Remark. Bellman–Ford–Moore is typically faster in practice.
􏰞Edge (v, w) considered in pass i + 1 only if d[w] updated in pass i. 􏰞If shortest path has k edges, then algorithm finds it after ≤ k passes.
47

Dynamic programming: quiz 8
Assuming no negative cycles, which properties must hold throughout Bellman–Ford–Moore?

A. Following successor[v] pointers gives a directed v↝t path.
B. If following successor[v] pointers gives a directed v↝t path,

then the length of that v↝t path is d[v].
C. Both A and B.
D. Neither A nor B.
48

Bellman–Ford–Moore: analysis
Claim. Throughout Bellman–Ford–Moore, following the successor[v]
 pointers gives a directed path from v to t of length d[v].


Counterexample. Claim is false!
􏰞Length of successor v↝t path may be strictly shorter than d[v].
consider nodes in order: t, 1, 2, 3
successor[2] = 1 successor[1] = t
d[2] = 20 d[1] = 10 d[t] = 0 2 10 1 10 t
1 3
successor[3] = t d[3] = 1
49
1

Bellman–Ford–Moore: analysis
Claim. Throughout Bellman–Ford–Moore, following the successor[v]
 pointers gives a directed path from v to t of length d[v].



Counterexample. Claim is false!
􏰞Length of successor v↝t path may be strictly shorter than d[v].
consider nodes in order: t, 1, 2, 3
successor[2] = 1 successor[1] = 3
d[2] = 20 d[1] = 2 d[t] = 0
2 10 1 10 t
1 3
successor[3] = t d[3] = 1
50
1

Bellman–Ford–Moore: analysis
Claim. Throughout Bellman–Ford–Moore, following the successor[v]
 pointers gives a directed path from v to t of length d[v].


Counterexample. Claim is false!
􏰞Length of successor v↝t path may be strictly shorter than d[v]. 􏰞If negative cycle, successor graph may have directed cycles.
consider nodes in order: t, 1, 2, 3, 4
d[3] = 10 d[2] = 8
322
1
9
3
5
d[t] = 0 t
4 8 1
d[4] = 11 d[1] = 5
51

Bellman–Ford–Moore: analysis
Claim. Throughout Bellman–Ford–Moore, following the successor[v]
 pointers gives a directed path from v to t of length d[v].



Counterexample. Claim is false!
􏰞Length of successor v↝t path may be strictly shorter than d[v]. 􏰞If negative cycle, successor graph may have directed cycles.
consider nodes in order: t, 1, 2, 3, 4
d[3] = 10 d[2] = 8 322
1
9
3
5
d[t] = 0 t
4 8 1
d[4] = 11 d[1] = 3
52

Bellman–Ford–Moore: finding the shortest paths
Lemma 6. Any directed cycle W in the successor graph is a negative cycle. Pf.
􏰞If successor[v] = w, we must have d[v] ≥ d[w] + 􏰟vw.

(LHS and RHS are equal when successor[v] is set; d[w] can only decrease; d[v] decreases only when successor[v] is reset)
􏰞Let v1 → v2 → … → vk → v1 be the sequence of nodes in a directed cycle W. 􏰞Assume that (vk, v1) is the last edge in W added to the successor graph.
􏰞Just prior to that:
 


 
 

d[v1] ≥ d[v2] ≥
⋮⋮
d[vk–1] ≥ d[vk] >
d[v2] d[v3]
d[vk] d[v1]
+ 􏰟(v1, v2) + 􏰟(v2, v3)

+ 􏰟(vk–1, vk) + 􏰟(vk, v1)
holds with strict inequality since we are updating d[vk]
􏰞Adding inequalities yields 􏰟(v1, v2) + 􏰟(v2, v3) + … + 􏰟(vk–1, vk) + 􏰟(vk, v1) < 0. ▪ W is a negative cycle 53 Bellman–Ford–Moore: finding the shortest paths Theorem 3. Assuming no negative cycles, Bellman–Ford–Moore finds
 shortest v↝t paths for every node v in O(mn) time and Θ(n) extra space. Pf. 􏰞The successor graph cannot have a directed cycle. [Lemma 6] 􏰞Thus, following the successor pointers from v yields a directed path to t. 􏰞Let v = v1 → v2 → ... → vk = t be the nodes along this path P. 􏰞Upon termination, if successor[v] = w, we must have d[v] = d[w] + 􏰟vw.
 (LHS and RHS are equal when successor[v] is set; d[·] did not change) 􏰞Thus,
 d[v1] 
 
 
 = d[v2] = d[v3] + 􏰟(v1, v2) + 􏰟(v2, v3) ⋮ + 􏰟(vk–1, vk) since algorithm terminated d[v2] ⋮⋮ d[vk–1] = d[vk] 􏰞Adding equations yields d[v] = d[t] + 􏰟(v1, v2) + 􏰟(v2, v3) + ... + 􏰟(vk–1, vk). ▪ min length of any v↝t path (Theorem 2) 0 length of path P 54 Single-source shortest paths with negative weights year worst case discovered by 1955 O(n4) Shimbel 1956 O(m n2 W) Ford 1958 O(m n) Bellman, Moore 1983 O(n3/4 m log W) Gabow 1989 O(m n1/2 log(nW)) Gabow–Tarjan 1993 O(m n1/2 log W) Goldberg 2005 O(n2.38 W) Sankowsi, Yuster–Zwick 2016 Õ(n10/7 log W) Cohen–Mądry–Sankowski–Vladu 20xx single-source shortest paths with weights between –W and W 55 6. DYNAMIC PROGRAMMING II ‣ sequence alignment ‣ Hirschberg′s algorithm ‣ Bellman–Ford–Moore algorithm ‣ distance-vector protocols ‣ negative cycles SECTION 6.9 Distance-vector routing protocols Communication network. 􏰞Node ≈ router. 􏰞Edge ≈ direct communication link. 􏰞Length of edge ≈ latency of link. 
 non-negative, but Bellman–Ford–Moore used anyway! Dijkstra’s algorithm. Requires global information of network. 
 Bellman–Ford–Moore. Uses only local knowledge of neighboring nodes. 
 Synchronization. We don’t expect routers to run in lockstep. The order in which each edges are processed in Bellman–Ford–Moore is not important. Moreover, algorithm converges even if updates are asynchronous. 57 Distance-vector routing protocols Distance-vector routing protocols. [ “routing by rumor” ] 􏰞Each router maintains a vector of shortest-path lengths to every other node (distances) and the first hop on each path (directions). 􏰞Algorithm: each router performs n separate computations, one for each potential destination node. 
 Ex. RIP, Xerox XNS RIP, Novell’s IPX RIP, Cisco’s IGRP, DEC’s DNA Phase IV, AppleTalk’s RTMP. 
 
 Caveat. Edge lengths may change during algorithm (or fail completely). suppose this edge 1 gets deleted s1v1t d(s) = 2 d(v) = 1 d(t) = 0 “counting to infinity” 58 Path-vector routing protocols Link-state routing protocols. not just the distance 􏰞 and first hop Each router stores the whole network topology. 􏰞Based on Dijkstra’s algorithm. 􏰞Avoids “counting-to-infinity” problem and related difficulties. 􏰞Requires significantly more storage. 
 
 Ex. Border Gateway Protocol (BGP), Open Shortest Path First (OSPF). 59 6. DYNAMIC PROGRAMMING II ‣ sequence alignment ‣ Hirschberg′s algorithm ‣ Bellman–Ford–Moore algorithm ‣ distance vector protocol ‣ negative cycles SECTION 6.10 Detecting negative cycles Negative cycle detection problem. Given a digraph G = (V, E), with edge lengths 􏰟vw, find a negative cycle (if one exists). 56 3 2 4 3 3 4 4 61 Detecting negative cycles: application Currency conversion. Given n currencies and exchange rates between pairs of currencies, is there an arbitrage opportunity? 
 Remark. Fastest algorithm very valuable! 0.741 * 1.366 * .995 = 1.00714497 USD 0.657 EUR 1.521 GBP CAD 1.049 An arbitrage opportunity 0.953 CHF 62 0.650 0.741 1.350 1.538 1.433 1.011 0.995 0.698 1.061 0.888 1.126 0.943 0.732 0.620 1.614 1.366 Detecting negative cycles Lemma 7. If OPT(n, v) = OPT(n – 1, v) for every node v, then no negative cycles. Pf. The OPT(n, v) values have converged ⇒ shortest v↝t path exists. ▪ 
 Lemma 8. If OPT(n, v) < OPT(n – 1, v) for some node v, then (any) shortest v↝t path of length ≤ n contains a cycle W. Moreover W is a negative cycle. 
 Pf. [by contradiction] 􏰞Since OPT(n, v) < OPT(n – 1, v), we know that shortest v↝t path P has exactly n edges. 􏰞By pigeonhole principle, the path P must contain a repeated node x. 􏰞Let W be any cycle in P. 􏰞Deleting W yields a v↝t path with < n edges ⇒ W is a negative cycle. ▪ x W c(W) < 0 v t 63 Detecting negative cycles Theorem 4. Can find a negative cycle in Θ(mn) time and Θ(n2) space. Pf. 􏰞Add new sink node t and connect all nodes to t with 0-length edge. 􏰞G has a negative cycle iff Gʹ has a negative cycle. 􏰞Case 1. [ OPT(n, v) = OPT(n – 1, v) for every node v ] By Lemma 7, no negative cycles. 􏰞Case 2. [ OPT(n, v) < OPT(n – 1, v) for some node v ] Using proof of Lemma 8, can extract negative cycle from v↝t path.
 (cycle cannot contain t since no edge leaves t) ▪ 56 G′ 0 3 2 4 3 3 t 0 0 0 4 4 64 Detecting negative cycles Theorem 5. Can find a negative cycle in O(mn) time and O(n) extra space. Pf. 􏰞Run Bellman–Ford–Moore on Gʹ for nʹ = n + 1 passes (instead of nʹ – 1). 􏰞If no d[v] values updated in pass nʹ, then no negative cycles. 􏰞Otherwise, suppose d[s] updated in pass nʹ. 􏰞Define pass(v) = last pass in which d[v] was updated. 􏰞Observe pass(s) = nʹ and pass(successor[v]) ≥ pass(v) – 1 for each v. 􏰞Following successor pointers, we must eventually repeat a node. 􏰞Lemma 6 ⇒ the corresponding cycle is a negative cycle. ▪ 
 Remark. See p. 304 for improved version and early termination rule.
 (Tarjan’s subtree disassembly trick)
 65 Dynamic programming: quiz 9 How difficult to find a negative cycle in an undirected graph?
 A. O(m log n) B. O(mn) C. O(mn + n2 log n) D. O(n2.38) E. No poly-time algorithm is known. Chapter 46 Data Structures for Weighted Ancestors Matching and with Linking Nearest Common Harold N. Gabow* Abstract. This paper shows that the weighted match- ing problem on general graphs can be solved in time O(n(m + n log n)), f or n and m the number of vertices and edges, respectively. This was previously known only for bipartite graphs. It also shows that a sequence of m nca and link operations on n nodes can be pro- cessed on-line in time O(ma(m, n)+n). This was previ- ously known only for a restricted type of link operation. 1. Introduction. This paper solves two well-known problems in data optimization; Edmonds ga weighted mat monds’ algor ingly fast ru [BD, GMG], ‘[GGS]. Edm Hungarian al ing on bipartit jan implemen n logn)) time structures and gives some related results. The starting point is the matching problem for graphs, which leads to the other problems. This section defines the problems detailed discussions are in [L, LP, PS]. ve the first polynomial-time algorithm for ching [El. Several implementations of Ed- ithm have been proposed, with increas- nning times: O(n3) [G73, L], O(mn log n) O(n(m log Tog log 2++,n + n log n)) onds’ algorithm is a generalization of the’ gorithm, due to Kuhn, for weighted match- e graphs [K55, K56]. Fredman and Tar- t the Hungarian algorithm in O(n(m + using Fibonacci heaps [FT]. They ask if general matching can be done in this time. Our first result is an affirmative answer: We show that a search in Edmonds’ algorithm can be implemented in time 66 Chapter 46 Data Structures for Weighted Matching and Nearest Common Ancestors with Harold N. Gabow* Linking Abstract. This paper shows that the weighted match- ing problem on general graphs can be solved in time O(n(m + n log n)), f or n and m the number of vertices and edges, respectively. This was previously known monds’ algorithm have been proposed, with increas- only for bipartite graphs. It also shows that a sequence of m nca and link operations on n nodes can be pro- cessed on-line in time O(ma(m, n)+n). This was previ- ously known only for a restricted type of link operation. [BD, GMG], O(n(m log Tog log 2++,n + n log n)) ‘[GGS]. Edmonds’ algorithm is a generalization of the’ 1. Introduction. This paper solves two well-known problems in data Hungarian algorithm, due to Kuhn, for weighted match- ing on bipartite graphs [K55, K56]. Fredman and Tar- jan implement the Hungarian algorithm in O(n(m + n logn)) time using Fibonacci heaps [FT]. They ask if optimization; detailed discussions are in [L, LP, PS]. Edmonds gave the first polynomial-time algorithm for weighted matching [El. Several implementations of Ed- ingly fast running times: O(n3) [G73, L], O(mn log n)