How to find the most probable traversal paths of a directed graph?

Question

Mathematics

Good afternoon.
There is such a problem:
A directed graph is given, one of the vertices of which is an "input" (no incoming edges), the other is an "output" (no outgoing edges). The graph may contain cycles. From the entrance you can go to any other vertex, and from any vertex - to the exit.
There is a set of options for "passing" this graph - a sequence of vertices through which you can go from input to output.
There is an assumption that there is some small basic set of such passages, and all options are a modification of one or another base case (i.e., first they followed it, then they went a little somewhere to the side, then they returned to this path again).
How can this base set be distinguished?
At the same time, it should be taken into account that the probability of transition from an arbitrary vertex to others depends on the context, on the history of previous transitions. Those. there can be two paths, for example, A -> B -> C and D -> B -> D, and where we go from B depends on where we came from.

Answer 1

Close the exit to the entrance. To each top to think up probabilities (yes though 1/n).
We get the Markov chain, it remains to find its ergodic distribution.
You just need to come up with a glitch in case the CM is periodic - but, perhaps, the standard SLAE regularization methods can handle this.

Answer 2

Possibly something like this?
- assign an identifier to each vertex
- represent the path as a sequence of vertices
- for each pair of paths - find common sequences of vertices
- for each path - find the length of the sequences that turned out to be common with others (although rather its relation to the length of the path).
It seems that it will be maximum for the path that satisfies our requirements.
But it's still kind of a crutch solution.
First, I am not sure of its correctness (there is no rigorous proof).
Secondly, it is required to create (or create on the go) a set of all possible paths from the entrance to the exit.
The icing on the cake is the complexity of the penultimate stage in N^2 * the complexity of Finding CommonSequences :-)