The Viterbi algorithm 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.