Given a directed graph, count the total number of paths of ANY length

Question

Given a directed graph, how to count the total number of paths of ANY possible length in it?

I was able to compute the answer using the adjacency matrix $A$, in which the number of paths of the length $n$ is the sum of elements $A^n$. But I have to calculate all $A^n$ for all possible $n$.

So is there any easier way, without computing large sparse matrix multiplication?

Sample graph:

Answer 1

Is it specifically a DAG? If so, process nodes in topological order, keeping count of how many different paths end at each node.

Answer 2

Henning's hint is really spot-on. There are no directed cycles. So this is a DAG. Now where does the graph "start"? It starts at node (1), correct? So updating the number of paths follows a recursive definition? How many paths of length one are there from node (1)? Count up the adjacencies.

Now count paths of length (2). To do this, how many adjacencies do each of (1)'s children have?

You really just traverse the thing like a tree and count.