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.path := [] endfor;
V0.weight := 0;
V0.path := [V0];
for X in S do {
for V in VV do V.newweight := -infinity endfor;
for U -> V in EE labelled X do
if U.path != [] and U.weight + weight(U->V) > V.newweight
then { V.newweight := U.weight + weight(U->V);
V.newpath := append(U.path, [V]) } endif endfor;
for V in VV do { V.weight := V.newweight;
V.path := V.newpath } endfor
} endfor;
V := the vertex with maximal V.weight;
return V.path
}
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.