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.