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?
3
-
1$\begingroup$ 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. $\endgroup$– MarsCommented Jul 25, 2020 at 15:50
-
$\begingroup$ @Mars Could you say more about those references please? Do they refer specifically to this problem and if so, in which context? $\endgroup$– SimdCommented Jul 25, 2020 at 18:50
-
$\begingroup$ 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. $\endgroup$– MarsCommented Jul 25, 2020 at 23:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
This idea is sufficiently well-known that I'm pretty sure I've seen papers just say things like "we can count the number of paths by dynamic programming" and stop there, with the expectation that the reader can fill in the details.
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.
-
$\begingroup$ Could you say more about the semiring problem? I couldn't see which part of the attached paper you were referring to (it doesn't seem to have anything with that name). $\endgroup$– SimdCommented Jul 25, 2020 at 18:47
-
$\begingroup$ @fomin Did you read and understand section 4 of the paper? (That paper might not use the exact phrase "semiring problem", that's just the paper I reach for reflexively whenever I want to link someone to info about graph semiring algorithms.) $\endgroup$ Commented Jul 25, 2020 at 18:55
-
2$\begingroup$ @fomin Here is another reference on semiring graph problems. Semiring algorithms generalize the idea of using dynamic progamming to efficiently compute some notion of sum over all paths in a graph. $\endgroup$ Commented Jul 25, 2020 at 19:00
-
$\begingroup$ Could you add some mathematical detail to your answer? In particular, why the counting problem OP is interested in is equivalent to a semiring problem from PL. $\endgroup$– SimdCommented Jul 26, 2020 at 11:16