Snakes and Active Contours - Bezier and Splines in Image Processing and Machine Vision - page 196

representing the likelihood of transitioning from one state to the next. In this
application, the multiplication of these very small numbers leads to a risk
of arithmetic underflow in the calculation of the Viterbi algorithm, which is
overcome by using the logarithm of probability and other scaling techniques.

Fig. 9.11. Example path in a trellis.

function Viterbi(T, w, s) // T = trellis

// w = costs
// s = start state

for each state x in X[T] // Initializations

d[x] := infinity
previous[x,0] := undefined // Index on state,hop

d[s] := 0
for each hop h in H[T] // H[T] is hops
for each state v in X[T] // Destination states
dist[v] := infinity // Flag v as trial
for each state u in X[T] // Source states
for each edge (u,v) outgoing from u
if d[u] + w(u,v) < dist[v]
d[v] := d[u] + w(u,v) // Flag v as known
previous[v,h] := u

Fig. 9.12. Pseudocode for Viterbi algorithm for finding the shortest path on a
trellis.