function Viterbi (in L : alphabet of symbols; S : string over L; G = : directed graph. Each edge has a label in L and a numerical weight. V0 : start vertex in G) return the path of maximal total weight through G starting in V0 outputting S { for (V in VV) do V.weight := -infinity endfor; V0.weight := 0; V0.previous:= null; for X in S do { for (V in VV) do V.newweight := -infinity endfor; for (U -> V in EE labelled X) do if (U.weight != -infinity and U.weight + weight(U->V) > V.newweight) then { V.newweight := U.weight + weight(U->V); V.newprev := U } endif endfor; for (V in VV) do { V.weight := V.newweight; V.prev := V.newprev } endfor } endfor; V := the vertex with maximal V.weight; return (traceback(V)) } traceback(V) { if (V == null) then return [] else return append(traceback(V.prev),[V]). } Loop invariant for main loop: Let Sk be the segment of S thus far examined. Then V.path is the maximal weight path through G starting in V0 outputting Sk, and V.weight is the weight of V.path. Time requirement. |S| * |VV| * maximal number of outarcs from a vertex with same label.