function Viterbi
   (in  L : alphabet of symbols;
        S : string over L;
        G = <VV,EE> : 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.