[The Viterbi algorithm ][1] is an algorithm for finding the most likely sequence of hidden states – called the Viterbi path.

**Question** If I am interested in list of several paths - optimal, sub-optimal, sub-sub-optimal etc... what should I do ? Are there some algorithms to solve it or to prove that this is hard (NP ?) problem ? 

There is naive way - actually Viterbi algorithm on each step keeps S paths (S-number of states), so at the final step we can choose list of candidates from these S paths.
But it will not give actually sub-optimal paths. 
The problem is rather clear - these paths will be different only for time moments near
to the end and same at the begining - so if actual sub-extremum is different at first positions, then we will never find it.

**Motivation** Consider the error-correcting code (used e.g. in GSM) which is two-step coding: 1) Add CRC 2) make convolutional coding.

The decoding for this code can be like this 1) List Viterbi for convolutional part 2) Check if any result satisy CRC constraint. 


  [1]: http://en.wikipedia.org/wiki/Viterbi_algorithm