Shortest Acyclic Path

Let $G = (V,E)$ be a directed acyclic graph, where each edge $(u, v)$ has a weight $wt(u, v) > 0$.

Topological sorting: vertices are numbered $v_1, v_2, ..., v_n$ such that for each $(v_i, v_j)$, we have $i< j$.

Let $s = v_1$ and $t = v_n$.

How do we compute the shortest path from $s$ to $t$?

Can we do better than Dijkstra algorithm, using the topological ordering of $G$?

Step 1: Structure of the Optimal Solution

Let $u_1, u_2, ..., u_k$ be all vertices that have an edge to $t$.

The last edge of the shortest path from $s$ to $t$ is $(u_i, t)$ for some $1 \leq i \leq k$.

If we know this index $i$, then the shortest path from $s$ to $t$ is equal to path from $s$ to $u_i$ followed by the edge $(u_i, t)$.

Since we don't know the index $i$, the length of the shortest path from $s$ to $t$ is equal: $\mathrm{min}_{1\leq i \leq k}$ (length of the shortest path from $s$ to $u_i$) + $wt(u_i, t)$. In other words, the shortest path from $s$ to $t$ contains the shortest path from $s$ to one of $u_1, u_2, ..., u_k$.

Step 2: Set up a Recurrence for the Optimal Solution

For $j = 1,2,..., n$, define $d(v_j) =$ length of a shortest path from $s$ to $v_j$. Since $v_n = t$, we want to compute $d(v_n)$.

Recurrence:

• $d(v_1) = 0$
• For $2 \leq j \leq n$, $d(v_j) = \mathrm{min}_{(v_i, v_j) \in E} {d(v_i) + wt(v_i, v_j)}$

Step 3: Solve the Recurrence "Bottom-Up"

First idea:

• To compute $d(v_n) = d(t)$, take all edges $(u_1, t), (u_2, t), ..., (u_k, t)$, and recursively compute $d(u_1), d(u_2), ..., d(u_k)$. From this, compute $d(v_n)$ as $d(v_n) = \mathrm{min}_{1\leq i \leq k} {d(u_i) + wt(u_i, t)}$

This is slow and takes $O(2^n)$.

Better approach:

d(v1) = 0
for i in range(2, n):
    k = indegree(vj)
    Let u1, u2, ..., uk be all the vertices that have an edge to vj
    d(vj) = infinity
    for i in range(1, k):
        d(vj) = min {d(vj), d(ui) + wt(ui, vj)}
return d(vn)

This running time here is $O(|V| + |E|)$.

Matrix Chain Multiplication

$A: p x q$ matrix, $B: q x r$ matrix, $C = A \cdot B: p x r$ matrix. $C$ has $pr$ entries, each of which can be computed in $O(q)$ time. So $C$ can be computed in $O(pqr)$ time. We define the cost of multiplying $A$ and $B$ to be $pqr$.

In general,

• $p_0, p_1, ..., p_n$: positive integers
• $A_1, A_2, ..., A_n$: matrices such that $A_i$ has $p_{i-1}$ rows and $p_i$ columns.

Compute the best order to compute the product of the matrices by minimizing the total cost.

Step 1: Structure of the Optimal Solution

Consider the best order to compute $A_iA_{i+1} \cdot ... \cdot A_j$. In the last step, we multiply: $(A_i \cdot ... \cdot A_k)$ and (A_{k+1} \cdot ... \cdot A_j), both of which are already computed.

Step 2: Set Up a Recurrence for the Optimal Solution

For $1\leq i \leq j \leq n$, define $m(i,j)$ = minimum cost to compute $A_i \cdot ... \cdot A_j$.

We want to compute $m(1,n)$.

If we know $k$, then $m(i,j) = m(i,k) + m(k+1, j) + p_{i-1}p_kp_j$.

But we do not know $k$, so try all values of $k$, $i \leq k \leq j-1$ and take the best one.

Recurrence:

• For $1\leq i \leq n$: $m(i, i) = 0$.
• For $1 \leq i < j \leq n$: $m(i,j) = \mathrm{min}_{i \leq k \leq j-1} m(i,k) + m(k+1, j) + p_{i-1}p_kp_j$

Step 3: Solve the Recurrence Bottom-Up

Compute, in this order,
$m(1, 1), m(2, 2), ..., m(n, n)$
$m(1, 2), m(2, 3), ..., m(n - 1, n)$
$m(1, 3), m(2, 4), ..., m(n - 2, n)$
$m(1, 4), m(2, 5), ..., m(n - 3, n)$
.
.
.
$m(1, n - 1), m(2, n)$
$m(1, n)$

Algorithms

for i = 1 to n do
    m(i, i) = 0
    for l = 2 to n do
        // Compute m(1, l), m(2, l + 1), ..., m(n - l + 1, n)
        for i = 1 to n - l + 1 do
            // Compute m(i, i + l - 1)
            j = i + l - 1
            // Compute m(i, j) using the recurrence
            m(i, j) = ∞
            for k = i to j - 1 do
                m(i, j) = min {m(i, j), m(i, k) + m(k + 1, j) + pi-1*pk*pj}
return m(1, n)

Running time is $\Theta(n^3)$

Longest Common Subsequence

We have two sequences:

• $X = (a,b,c,b,d,a,b)$
• $Y = (b,d,c,a,b,a)$

The sequence $Z = (b,c,d,b)$ is a subsequence of $X$ but not of $Y$.

LCS($X$, $Y$) is the longest subsequence of $X$ and $Y$: $(b,c,b,a)$ or $(b,d,a,b)$

Step 1: Structure of the Optimal Solution

$X = (x_1, x_2, ..., x_m)$ $Y = (y_1, y_2, ..., y_n)$

$Z = (z_1, z_2, ..., z_k) =$ LCS($X$, $Y$). Therefore $k \leq m, k \leq n$

• Case 1:
  • $z_k = x_m = y_n$ and $(z_1, z_2, ..., z_{k-1}) = \mathrm{LCS}(x_1x_2 ... x_{m-1}, y_1y_2 ... y_{n-1})$
• Case 2:
  • $x_m \neq y_n$
  • Case 2a): $z_k \neq x_m$
    • $(z_1, z_2, ..., z_{k}) = \mathrm{LCS}(x_1x_2 ... x_{m-1}, y_1y_2 ... y_{n})$
  • Case 2b): $z_k \neq y_n$
    • $(z_1, z_2, ..., z_{k}) = \mathrm{LCS}(x_1x_2 ... x_{m}, y_1y_2 ... y_{n-1})$
  • We compute both 2a and 2b as we don't know which case we fall under

Step 2: Set up a recurrence for the Optimal Solution

For $0 \leq i \leq m$ and $0 \leq j \leq n$ define $c(i,j) =$ length of $\mathrm{LCS}(x_1x_2...x_i, y_1y_2...y_j)$

We want to compute $c(m,n)$

Recurrence:

• If $i=0$ or $j=0$, $c(i,j) = 0$
• If $i\geq 1, j \geq 1$ and $x_i = y_j$, $c(i,j) = 1 + c(i-1, j-1)$
• If $i\geq 1, j \geq 1$ and $x_i \neq y_j$, $c(i,j) = max{c(i-1,j), c(i, j-1)}$

Step 3: Solve the recurrence "Bottom-Up"

Fill in the matrices $c (i, j)$ for $0 \leq i \leq m$ and $0 \leq j \leq n$.

• First row:
  • $c(0, 0) = c(0, 1) = ... = c(0, n) = 0$
• First column:
  • $c(0, 0) = c(1, 0) = ... = c(m, 0) = 0$

Then fill in the matrix, row by row, in each row from left to right.

Algorithm

for i = 0 to m do
    c(i, 0) = 0
for j = 0 to n do
    c(0, j) = 0
for i = 1 to m do
    for j = 1 to n do
        if xi = yj then
            c(i, j) = 1 + c(i - 1, j - 1)
        else
            c(i, j) = max {c(i - 1, j), c(i, j - 1)}}
return c(m, n)

Running time: $O(m*n)$

Space: $O(m*n)$

But if we only want to compute $C(m, n)$, we only need the current row and the previous row. Hence, Space: $O(m+n)$

General Structure

In general, when we solve a problem using dynamic programming, we go through the following steps:

1. Understand the structure of the optimal solution. Show that there is an optimal substructure: an optimal solution “contains” optimal solutions for subproblems (which are smaller problems).
2. Set up a recurrence for the optimal solution. We know from Step 1 that an optimal solution can be obtained from optimal solutions for subproblems. Use this to derive recurrence relations.
3. Solve the recurrence bottom-up. First solve the smallest subproblems (usually the base case of the recurrence). Then solve the second smallest subproblems. Then solve the third smallest subproblems, etc.

Do not use a recursive algorithm!

All-Pairs Shortest Paths

Let $G = (V, E)$ be a directed graph, where $V = {1, 2, ..., n}$. Each edge $(i, j)$ has a weight $wt(i, j) > 0$.

For all $i$ and $j$, compute the weight of a shortest path in $G$ from $i$ to $j$, which we denote by $\gamma_G (i, j)$.

Step 1: Structure of the Optimal Solution

Consider the shortest path from $i$ to $j$, and assume this path has at least one interior vertex. Let $k$ be the largest interior vertex.

• shortest path from $i$ to $k$, all interior vertices are $\leq k-1$
• shortest path from $k$ to $j$, all interior vertices are $\leq k-1$

Step 2: Set up a recurrence for the Optimal Solution

For $i \leq i \leq n$, $1 \leq j \leq n$, $0 \leq k \leq n$, be the length of the shortest path from $i$ to $j$, all of whose interior vertices are vertices are $\leq k$.

We want to compute $dist(i,j,n) = \gamma_G (i,j)$ for all $1 \leq i \leq n, 1 \leq j \leq n$.

Recurrence:

• For $1 \leq i \leq n, \mathrm{dist}(i,i, 0) = 0$

• For $1 \leq i \leq n, 1 \leq j \leq n, i \neq j$

• $dist (i,j,0) = {wt(i,j) if (i,j) is an edge, \infty otherwise}$

• For $1 \leq i \leq n, 1 \leq j \leq n, 1 \leq k \leq n$, $dist(i,j,k) = min {dist(i, j, k-1), dist(i, k, k-1) + dist(k, j, k-1)}$.

Algorithm: Floyd-Warshall

for i = 1 to n do
    for j = 1 to n do
        if i = j then
           dist(i, j, 0) = 0
        else
            dist(i, j, 0) = +infinity
for all edges (i, j) do
    dist(i, j, 0) = wt(i, j)
for k = 1 to n do
    for i = 1 to n do
        for j = 1 to n do
            dist(i, j, k) = min {dist(i, j, k - 1), dist(i, k, k - 1) + dist(k, j, k - 1)}

$O(n^3)$

Final Remarks

Dynamic Programming solutions work for finding shortest path, minimum cost, but not longest or max. That is a NP-Hard problem