How to find next to optimal path in hidden Markov model or what should be LIST-Viterbi algorithm? 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. 
 A: The Viterbi algorithm works by maintaining, at all times between $[t,T]$, for all states $S^k_t$, the likelihood of the maximum likelihood path between this state and any state $S_T$. You can run it a second time, but this time, maintain the likelihood of reaching any state $S_T$ following a path that maximizes likelihood while being less likely than the one previously calculated. To avoid dealing with exact duplicates, you can add a very small noise to every edge.
In maybe-compiling C++,
// do something for the case t = T    
for(int t = T-1; t > 0; --t) {
   ll2[k][t] = NEGATIVE_INFINITY;
   for(int i = 0; i < K; ++i) {
      // we could make this transition then follow the 2nd best path
      double a = ll_transition[t][k][i] + ll2[i][t+1];
      if (a < ll[k][t]) // we don't want a maximum likelihood path
         ll2[k][t] = max( ll2[k][t], a );
      // or we could make a transition then follow the best path
      a =  ll_transition[t][k][i] + ll[i][t+1]
      if (a < ll[k][t]) // we don't want a maximum likelihood path
         ll2[k][t] = max( ll2[k][t], a )
   }
}
// do something for the case t = 0

