ビタビアルゴリズム
元の状態について、その状態までのビタビ経路の確率は既知である。この場合も同様に、その状態で現在の観測値が得られる確率と次の状態に遷移する確率をその時点までのビタビ経路の確率にかけ、それが valmax の現在値よりも大きい場合は valmax を置き換える。ビタビ経路そのものは、最大値に対応した状態系列を argmax として保持する。このように計算された3つ組 (prob, v_path, v_prob) が U に格納され、全ての可能な次の状態について U の計算が完了した時点で、それを T に代入する。
最後に総和と最大をとる(最後の実際の観測結果を処理した後に仮想的な観測結果を処理するようにすれば、メインループ内でもできる)。
当初の例にこのアルゴリズムを適用する場合、次のようになる。
これにより、['walk', 'shop', 'clean'] という並びの全体確率は 0.033612、ビタビ経路は ['Sunny', 'Rainy', 'Rainy', 'Rainy'] となる。3つ目の観測結果から3つ目の状態と4つ目の状態への遷移が求められるので、ビタビ経路には4つ目の状態も含まれている。つまり、与えられた観測結果から、友人が散歩に出た初日は晴れだったが、その後雨が降り続いている可能性が最も高いと言える。
このアルゴリズムを実装する際、多くの言語では浮動小数点数を使うと思われるが、p が小さいと結果としてアンダーフローを生じる危険性がある。これを防ぐ技法として、確率の対数をとり、計算を全てその対数値で行う方法がある。最終的な値が対数で得られたら、それに適切な指数関数を適用すれば、真の値が求められる。