The previous chapters have seen some very elegant algorithms that are very niche: they can only be used for specific types of problems. We now turn to the two sledgehammers of algorithm design: dynamic programming, and linear programming, techniques of very broad applicability that can be invoked when more specialized methods fail. However, this flexibility often comes with a cost in efficiency.
At the conclusion of our study of shortest paths, we observed the problem is especially easy in directed acyclic graphs (DAGs). Let us revisit this case.
A DAG's nodes can always be linearized: arranged along a line, so that all edges go from left to right.
Suppose, in Figure 6.1, we want to find the minimum distance from node $S$ to $D$. The only way to get to it is through its predecessors, $B$ or $C$, so to find the shortest path to $D$, we only need to compare these two routes:
$$ \text{dist}(D)=\min\{\text{dist}(B)+1,\text{dist}(C)+3\}. $$
A similar relation can be written for every node. If we compute the dist values in a left to right order, then we can be sure by the time we get to a node $v$, we already have all the information needed to compute $\text{dist}(v)$. We are therefore able to compute all distances in a single pass:
initialize all dist(v) values to infinity
dist(s) = 0
for each v in V\\{s}, in linearized order:
for each (u, v) in E:
dist(v) = min(dist(u) + l(u,v), dist(v))
Notice that this algorithm is solving a collection of subproblems, $\{\text{dist}(u): u \in V\}$. We start with the smallest of them, dist(s), since we know its answer to be 0. We then proceed with progressively larger subproblems — distances further and further along in the linearization.
This is a very general technique, where we compute some function of the values of the predecessors at each node. Instead of computing the minimum, we could easily change our algorithm to find the longest paths, or get the product instead of sum inside the brackets.
<aside> 💡 Dynamic programming is a very powerful algorithmic paradigm in which the problem is solved by identifying a collection of subproblems, and tackling them one by one, smallest first, using the answers to smaller problems to help figure out larger ones. In dynamic programming, we are not always given a DAG; the DAG is implicit. Its nodes are the subproblems we define, and its edges are the dependencies between the subproblems: if to solve subproblem $B$, we need the answer to subproblem $A$, then there is an edge from $A$ to $B$. In this case, $A$ is thought of as a smaller subproblem than $B$.
</aside>
Given a sequence of numbers $a_1,\cdots,a_n$, find an increasing subsequence of the greatest length, where a subsequence is any subset of the numbers, taken in the form, $a_{i1},a_{i2},\cdots,a_{ik}$, where $1\leq i_1<i_2<\cdots<i_k\leq n$, where the numbers are getting strictly larger. For example, given the sequence $5, 2, 8, 6, 3, 6, 9, 7$, the answer would be $2, 3, ,6, 9$.
$$ 5,\underline{2},8,6,\underline{3},\underline{6},\underline{9},7 $$
The graph shows all permissible transitions, where there is a directed edge $(i,j)$ whenever it is possible for $a_i$ and $a_j$ to be consecutive elements in an increasing subsequence, or in other words, $i<j$ and $a_i<a_j$.