# Reference for counting the number of paths in a DAG

Given a connected DAG I know how to compute the number of paths between two nodes. See e.g. Counting number of paths between two vertices in a DAG .

Is there a reference or name for the algorithm? If not, are there well known applications?

• I don't know the algorithm, but these books have relevant material, I believe: Kemeny and Snell, Finite Markov Chains (chapter 1); Flajolet and Sedgewick, Analytical Combinatorics. – Mars Jul 25 '20 at 15:50
• @Mars Could you say more about those references please? Do they refer specifically to this problem and if so, in which context? – fomin Jul 25 '20 at 18:50
• The first reference contains a methods for counting paths in DAGs. I'm pretty sure that the second will, too. I don't know whether they are what you want. – Mars Jul 25 '20 at 23:28

It is also the semiring problem for $$\mathbb{N}$$ with the usual $$+$$ and $$\times$$, and can be extended to cyclic graphs by extending the value set to $$\mathbb{N} \cup \infty$$ and adding a suitable $$a^*$$ operator.