# Discrete optimization on a Markov chain graph

My question arose due to using Markov chains in computer linguistics.

Let $$X_ {0}, X_ {1}, X_ {2}, \ldots$$ be a homogeneous Markov chain with $N$ states $S_ {1}, \ldots, S_ {N}$, the initial probability vector $\pi=(\pi_{1}, \ldots, \pi_{N})$ where $\pi_{i}=\mathbb{P}(X_{0}=S_{i})$, and the transition probability matrix $A=(a_{ij})$ where $a_{ij}=\mathbb{P} (X_{n}=S_{j} | X_{n-1}=S_{i})$, $a_{ij}$ is independent of $n$.

The problm is to find several (e.g. $r=10$) most probable finite sequences of events-states of the chain (let, for simplicity, the events-states be of the given fixed length $m$ and starting from the initial state, let they be even different; further one can generalize it to the case of finite sequences of variable length and starting from some $k$th state, etc.). Let me describe what I mean in detail. $$\mathbb{P}(X_{0}=S_{i_ {0}}, X_{1}=S_{i_{1}}, \ldots, X_{m-1}=S_{i_{m-1}})=\pi_{i_{0}} a_{i_{0}i_{1}} a_{i_{1}i_{2}} \ldots a_{i_{m-2}i_{m-1}}.$$ Let us assume that the states in the above chain $S_{i_{0}}, S_{i_{1}}, \ldots, S_{i_{m-1}}$ are pairwise distinct (for simplicity). Of course, one can stupidly count all such probabilities, sort them in the descending order, and print the first $r=10$ finite sequences of length $m$ as the answer. But this is a very 'wasteful' solution, it's a brute-force algorithm. Can it be optimized?

My considerations are as follows. Let us logarithm (on any base greater than one), then the product will turn into the sum: $$\log\mathbb{P}(X_{0}=S_{i_ {0}}, X_{1}=S_{i_{1}}, \ldots, X_{m-1}=S_{i_{ m-1}})= \log \pi_{i_{0}}+\log a_{i_{0}i_{1}}+\log a_{i_{1}i_{2}}+\ldots+\log a_{i_{m-2}i_{m-1}}.$$ Then assuming that in the directed graph (with loops) of our homogeneous Markov chain these edges are weighted with these logarithms of probabilities, one obtain the problem of finding the 'longest' path of the given length $m-1$ in this graph, more precisely, several 'longest' $r=10$ paths of the given length $m-1$. Multiplying all these logarithms by (-1) one obtain the problem on the shortest path of the given length in the graph, or several shortest paths. It turns out that one have to solve the problem of the shortest path of the given length in the directed graph with loops? How such problems can be effectively solved?