Counting number of paths between two vertices in a DAG

Question

I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.

Answer 1

Here is a dynamic programming algorithm. Given a graph $G = (V, E)$ and two vertices $u, v \in V$. We define the recursive function $C:V\rightarrow \mathbb{N}$, such that $C(w)$ is the number of paths from $w$ to $v$. Note that we are looking for the value of $C(u)$. We set $C(v) = 1$ and $C(w)=0$ for each vertex $w \neq v$ with out-degree equal to zero. For each other vertex $w\in V\setminus \{v\}; \delta^+(w)>0$ we can compute the value of $C(w)$ using the following formula $$C(w) =\sum\limits_{x\in N^+(w)}C(x),$$ where $N(w)$ is the set of neighbors of $w$.

Note that $C(w)$ depends merely on the value of $C$ at the neighbors of $w$ and since a DAGs define a natural ordering over the vertices of the graph (namely the topological ordering), such that all neighbors of a vertex are smaller that it upon this ordering, we can compute $C(w)$ for all vertices $w$ according to their topological ordering using dynamic programming.

The correctness of the solution can be proved with induction over the diameter of the graph or over the length of the longest path from $u$ to $v$ for example.

The running time can be bounded by. $O(n+m)$ and the space complexity by $O(n)$.