# 算法设计与分析笔记0x08 —— 动态规划(2)

## Sequence Alignment: Linear Space

How can we use $\Theta(m+n)$ space and $O(mn)$ time.

• Compute OPT(i,*) from OPT(i-1,*)
• 可以把i-1以下的数据删掉，但是这种方法不可回溯

Edit distance graph

• Let f(i,j) be shortest path from (0,0) to (i,j).
• Observation: f(i,j) = OPT(i,j)
• Can compute f(*,j) for any j in O(mn) time and O(m+n) space.

• Let g(i,j) be shortest path from (i,j) to (m,n).
• Can compute g(*, j) by reversing the edge orientations and inverting the roles of (0,0) and (m,n): O(mn) time and O(m+n) space.
• What our goal now is to find shortest path from (0,0) to (m,n), which is f(i,j) + g(i,j).
• Let q be an index that minimizes f(q, n/2) + g(q, n/2). Then, the shortest path from (0, 0) to (m, n) uses (q, n/2).
• Find index q that minimizes f(q, n/2) + g(q, n/2) using DP.
• Recursively compute optimal alignment in each piece.

### Analysis

• Combine divide and conquer with dynamic programming
• O(mn) 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.

Claim: T(m,n)≤ 2cmn
– Base cases: m=2 or n=2.
– Inductive hypothesis: T(m’,n’)≤ 2cm’n’ with m’<m and n’<n

## Shortest Paths

Dijkstra limitation: positive path weight.
Now let’s allow negative weight(occurred in financial case)
Goal: Find path from s to t with largest gains or smallest loss.

Plus the negative number to removing negative edge.(shortest changed, because the numbers of edges of different path are different)

Negative cost cycle sum of cost is negative.

• If the graph contains negative cost cycle, there is no shortest path.

### Problem Structure

OPT(i,v) = length of shortest v-t path P using at most i edges

• Base case:
• v = t, OPT(i,v) = 0
• i = 0, OPT(i,v) = ∞
• Case 1: P uses at most i-1 edges.
• OPT(i,v) = OPT(i-1,v)
• Case 2: P uses exactly i edges.
• if (v, w) is first edge, then OPT uses (v, w), and then selects best w-t path using at most i-1 edges

### Algorithm

• $\Theta(mn)$ time, $\Theta(n^2)$ space.

Analysis

### Bellman-Ford

Analysis

• No need to check edges of the form (v, w) unless M[w] changed in previous iteration.
• O(n) extra space
• Time: O(mn) worst case, but substantially faster in practice.
• Throughout the algorithm, M[v] is length of some v-t path, and after i rounds of updates, the value M[v] is no larger than the length of shortest v-t path using ≤ i edges.

## Distance Vector Protocol

Dijkstra’s algorithm. Requires global information of network.
Bellman-Ford. Use only local knowledge of neighboring nodes.

Counting to infinity -> Path Vector Protocol

## Negative Cycles in Graphs

Goal: find out negative cycles(if one exists)
Lemma If OPT(n,v) = OPT(n-1,v) for all v, then there is no negative cycle with a path to t.

• OPT(n,v) = OPT(n-1,v) => OPT(i,v) = OPT(n-1,v) for i ≥ n
• But negative cycle in a path implies that OPT(i,v) always decreases as i increases

Lemma If OPT(n,v) < OPT(n-1,v) for some node v, then (any) shortest path from v to t contains a cycle W. Moreover W has negative cost.

• Since OPT(n,v) < OPT(n-1,v), we know the shortest v-t path P has exactly n edges.
• By pigeonhole principle, P must contain a directed cycle W.
• Deleting W yields a v-t path with < n edges => W has negative cost.

Theorem Can detect negative cost cycle in O(mn) time.

• Add new node t and connect all nodes to t with 0-cost edge.
• Check if OPT(n, v) = OPT(n-1, v) for all nodes v.
• if yes, then no negative cycles
• if no, then extract cycle from shortest path from v to t