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 QAnswer: 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.