Maximum number of path for acyclic graph with start and end node Say given an acyclic graph with n nodes,
which includes a starting node s0 and ending node e0,
what is the maximum number of path from s0 to e0?
If you want the maximum number for any graph (of some size), that's easy. Take the maximal graph with N vertices $v_1...v_n$ where $v_1$ is $s_o$ and $v_n$ is $e_o$, with edges $v_i \rightarrow v_j$ for all $1 \le i &lt; j \le n$. Now any sequence $v_1v_{p_1}...v_{p_k}v_n$ where $1 &lt; p_1 &lt; p_2 &lt; ... &lt; p_k &lt; n$ is a path from $s_0$ to $e_0$. Or to put it another way, any subset of the vertices which includes both $s_0$ and $e_0$ uniquely defines a path (by sorting the vertices into index order); there are $2^{n-2}$ such subsets.

If you have a specific graph, then you can use the following procedure to compute the number of paths:

1) Topologically sort the vertices. The first vertex in the topological sort must be $s_0$ and the last one must be $e_0$ (unless I misunderstand your question; if so, just use the portion of the topological sort between the start and end vertex.)

2) Associate a count with each vertex. Set the count associated with $e_0$ to be 1.

3) For each vertex in the topological sort in reverse order, starting with the vertex just before $e_0$, set its count to the sum the counts of all of its neighbour vertices.

4) The count associated with $s_0$ is the total number of possible paths.

You don't actually have to do the topological sort. You can just depth-first-search the tree starting with $s_0$, computing the counts recursively.
I suppose the graph is connected, otherwise there might be no path at all.
In general there are infinitely many paths starting from s0 and ending in e0 if you not require them to be simple. If you require them to be simple there is only one.