Dynamic programming

If a directed graph is acyclic, dynamic programming can be applied to it. For example, we can efficiently solve the following problems concerning paths from a starting node to an ending node:

• how many different paths are there?
• what is the shortest/longest path?
• what is the minimum/maximum number of edges in a path?
• which nodes certainly appear in any path?

Counting the number of paths

As an example, let us calculate the number of paths from node 1 to node 6 in the following graph:

There are a total of three such paths:

• $1 \rightarrow 2 \rightarrow 3 \rightarrow 6$
• $1 \rightarrow 4 \rightarrow 5 \rightarrow 2 \rightarrow 3 \rightarrow 6$
• $1 \rightarrow 4 \rightarrow 5 \rightarrow 3 \rightarrow 6$

Let paths(x) denote the number of paths from node 1 to node $x$. As a base case, paths(1)=1. Then, to calculate other values of paths(x), we may use the recursion

\[ \texttt{paths}(x) = \texttt{paths}(a_1)+\texttt{paths}(a_2)+\cdots+\texttt{paths}(a_k) \]

where $a_1,a_2,\ldots,a_k$ are the nodes from which there is an edge to $x$. Since the graph is acyclic, the values of $\texttt{paths}(x)$ can be calculated in the order of a topological sort. A topological sort for the above graph is as follows:

Hence, the numbers of paths are as follows:

For example, to calculate the value of paths(3), we can use the formula paths(2)+paths(5), because there are edges from nodes 2 and 5 to node 3. Since paths}(2)=2 and paths}(5)=1, we conclude that paths}(3)=3.

Extending Dijkstra's algorithm

A by-product of Dijkstra's algorithm is a directed, acyclic graph that indicates for each node of the original graph the possible ways to reach the node using a shortest path from the starting node. Dynamic programming can be applied to that graph. For example, in the graph

the shortest paths from node 1 may use the following edges:

Now we can, for example, calculate the number of shortest paths from node 1 to node 5 using dynamic programming:

Representing problems as a graphs

Actually, any dynamic programming problem can be represented as a directed, acyclic graph. In such a graph, each node corresponds to a dynamic programming state and the edges indicate how the states depend on each other.

As an example, consider the problem of forming a sum of money $n$ using coins \( \{c_1,c_2,\ldots,c_k\} \). In this problem, we can construct a graph where each node corresponds to a sum of money, and the edges show how the coins can be chosen. For example, for coins \(\{1,3,4\}\) and $n=6$, the graph is as follows:

Using this representation, the shortest path from node 0 to node $n$ corresponds to a solution with the minimum number of coins, and the total number of paths from node 0 to node $n$ equals the total number of solutions.