Consider a directed acyclic graph $\mathcal{G} = (\mathcal{N},\mathcal{E})$. Assume that the graph is very large (on the order of 10000 nodes and edges).
Let there be a set of nodes termed starting nodes denoted by $\mathcal{N}_s\subseteq\mathcal{N}$ and a set of nodes termed terminal nodes denoted by $\mathcal{N}_t\subseteq\mathcal{N}$. Consider the set of all paths that start from a node in $\mathcal{N}_s$ and end in a node in $\mathcal{N}_t$. Denote this set by $\mathcal{P}$.
Goal: Derivation of a procedure that allows one to uniformly sample paths from the set $\mathcal{P}$ without having to construct $\mathcal{P}$ explicitly.
Ideas: Of course, listing all such paths is computationally intractable preventing one from just being able to sample from a table of all paths. I am wondering if one can construct a procedure that involves sampling edges of the graph at random (without replacement) until one obtains a path that satisfies the condition that it starts in $\mathcal{N}_s$ and ends in $\mathcal{N}_t$ such that the procedure samples paths uniformly from $\mathcal{P}$.
I've sketched out such a procedure for a small graph below. The top (green) nodes are the nodes $\mathcal{N}_s$ whereas the bottom (purple) nodes are the nodes $\mathcal{N}_t$. At each step of the procedure a single edge is sampled at random (denoted by the red edges). A check is done to see if it is a path that satisfies the condition, if not, sample a new edge (without replacement) and check again. Repeat until we find a path. If the addition of a single edge results in multiple paths, pick one at random. We add this path to our set of sampled paths, call it $\mathcal{\bar P}$, and repeat the process.
Question: Does such a procedure result in uniformly sampled paths from $\mathcal{P}$? If not, are there procedures that do so without requiring one to construct $\mathcal{P}$?