## 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.