This is a quick description of the Viterbi algorithm, aka dynamic programming algorithm. Text is based from the doc/viterbi.txt file (once) included in the FFmpeg tree, text by Michael Niedermayer.

Problem description

Assume we have a 2D table:

    O   O   O   O   O   O   O

    O   O   O   O   O   O   O

    O   O   O   O   O   O   O

    O   O   O   O   O   O   O

That table has edges connecting points from each column to the next column and each edge has a score (only some edge and scores shown to keep it readable):

    O--5--O-----O-----O-----O-----O
     2   / 7   / \   / \   / \   /
      \ /   \ /   \ /   \ /   \ /
    O7-/--O--/--O--/--O--/--O--/--O
     \/ \/ 1/ \/ \/ \/ \/ \/ \/ \/
     /\ /\ 2\ /\ /\ /\ /\ /\ /\ /\
    O3-/--O--/--O--/--O--/--O--/--O
      / \   / \   / \   / \   / \
     1   \ 9   \ /   \ /   \ /   \
    O--2--O--1--O--5--O--3--O--8--O

Our goal is to find a path from left to right through it which minimizes the sum of the score of all edges. Of course left/right is just a convention here as it could be top/down too. Similarly the minimum could be the maximum by just flipping the sign.

Example of a path with scores:

    O   O   O   O   O   O   O

>---O.  O   O  .O-2-O   O   O
      5.     .7      .
    O   O-1-O   O   O 8 O   O
                       .
    O   O   O   O   O   O-1-O---> (sum here is 24)

Viterbi algorithm

The Viterbi algorithm simply solves column by column. For the previous column each point has a best path and an associated score:

    O-----5     O
     \
      \
    O  \  1     O
        \/
        /\
    O  /  2     O
      /
     /
    O-----2     O

To move one column forward we just need to find the best path and associated scores for the next column.

Here are some edges we could choose from:

    O-----5--3--O
     \      \8
      \       \
    O  \  1--9--O
        \/  \3
        /\     \
    O  /  2--1--O
      /     \2
     /        \
    O-----2--4--O

Finding the new best paths and scores for each point of our new column is trivial given we know the previous column best paths and scores:

    O-----0-----8
     \
      \
    O  \  0----10
        \/
        /\
    O  /  0-----3
      /     \
     /        \
    O     0     4

The Viterbi algorithm continues exactly like this column for column until the end and then just picks the path with the best score (above that would be the one with score 3).