Example of Viterbi algorithm

Input string: ABBA
```Vertex: Step 0 -> A -> Step 1 -> B -> Step 2 -> B ->  Step 3 -> A -> Step 4
P.weight  0    _/_/_    -infty  _/7/_   7    11/14/_  14     _/_/10   10
.prev    P              _              Q              Q               R
Q.weight -inf  5/_/_     5      _/9/12 12    _/16/15  16     19/20/_  20
.prev                   P              R              Q               Q
R.weight -inf  2/_/_     2      _/_/5   5              8     16/22/_  22
.prev                   P              R    8/_/8     P               Q
```
Answer: traceback(R) = [P,R,Q,Q,R] of weight 22.

The labels under the letters are costs of the various extended best paths. For instance, the label "11/14/_" under the second B on the line "P.weight" means that in traversing the second B arc from step 2 to step 3, there is a path that produces "ABB" of total cost 11 whose last arc is P->P; a path that produces "ABB" of total cost 14 whose last arc is Q->P; and no path that produces "ABB" whose last arc is R->P.