Editing Viterbi algorithm (section)

== Pseudocode ==

 '''function''' Viterbi(states, init, trans, emit, obs) '''is'''
     '''input''' states: S hidden states
     '''input''' init: initial probabilities of each state
     '''input''' trans: S × S transition matrix
     '''input''' emit: S × O emission matrix
     '''input''' obs: sequence of T observations
 
     prob ← T × S matrix of zeroes
     prev ← empty T × S matrix
     '''for''' '''each''' state s '''in''' states '''do'''
         prob[0][s] = init[s] * emit[s][obs[0]]
 
     '''for''' t = 1 '''to''' T - 1 '''inclusive do''' ''// t = 0 has been dealt with already''
         '''for''' '''each''' state s '''in''' states '''do'''
             '''for''' '''each''' state r '''in''' states '''do'''
                 new_prob ← prob[t - 1][r] * trans[r][s] * emit[s][obs[t]]
                 '''if''' new_prob > prob[t][s] '''then'''
                     prob[t][s] ← new_prob
                     prev[t][s] ← r
 
     path ← empty array of length T
     path[T - 1] ← the state s with maximum prob[T - 1][s]
     '''for''' t = T - 2 '''to''' 0 '''inclusive do'''
         path[t] ← prev[t + 1][path[t + 1]]
 
     '''return''' path
 '''end'''

The time complexity of the algorithm is <math>O(T\times\left|{S}\right|^2)</math>. If it is known which state transitions have non-zero probability, an improved bound can be found by iterating over only those <math>r</math> which link to <math>s</math> in the inner loop. Then using [[amortized analysis]] one can show that the complexity is <math>O(T\times(\left|{S}\right| + \left|{E}\right|))</math>, where <math>E</math> is the number of edges in the graph, i.e. the number of non-zero entries in the transition matrix.