向前算法有一种简单的变体，称为Viterbi算法，这种算法可以让我们同时考虑所有单词，并且还能计算出最佳路径。Viterbi这个术语在语音和语言处理中用得很普遍，但正如向前算法一样，Viterbi算法确实也是经典的动态规划算法的一种很标准的应用，并且它看起来很像最小编辑距离算法。Viterbi算法首先由Vintsyuk（1968）应用在语音识别中，并且这种算法也有像Kruskal（1983）所说的那种“多重独立发现和发表的引人注目的历史”。Viterbi的名字在语音识别中使用得非常普遍，尽管人们也使用诸如动态规划对齐（Dynamic Programming Alignment,简称DP对齐）、动态时间偏移（Dynamic time warping）以及一遍解码（one-pass decoding）等术语。Viterbi算法这个术语应用于单个词的加权自动机和隐马尔可夫模型的解码，也应用于连续语音等复杂问题的解码。在此仅简单介绍怎样使用这种算法来发现通过构成单词网络的最佳路径，从而对于给定的单词符号串观察序列选出具有最佳概率的单词。

我们在这里介绍的这种Viterbi算法取一个单独的加权自动机和所观察音子的集合O=（O₁O₂O₃…Ot，）作为输入，返回具有最佳概率的状态序列q=（q₁q₂q₃…qt）及其概率。我们可以这样来建立一个单独的加权自动机，在这个加权自动机中，用一个初始状态和一个终结状态把knee,need,new和neat这四个单词的发音网络并行地结合起来。图1 说明了这些网络结合的情况。

图1 把单词need,neat,new和knee的发音网络结合为一个单独的加权自动机。单词的概率一般并不是该单词的发音网络的一部分，但在这里都加上了单词的概率，这样做主要是为了使我们对于Viterbi算法的解释变得简单一些

图2 说明了这个Viterbi算法的伪代码。正如在最小编辑距离算法和向前算法中那样，Viterbi算法也建立了一个概率矩阵，矩阵的列（column）表示每个单词的索引号t，矩阵的行表示状态图中的每个状态。正如在向前算法中那样，对于把这4个单词结合起来的这个单独的自动机中的每个状态qi，每个列都有一个单元。事实上，Viterbi算法中的代码与向前算法中的代码一样，只不过是做了上述的两个修改而已。向前算法把前面所有路径的总和放到当前单元中，而Viterbi算法则把前面所有路径中最大的放到当前单元中。

算法首先建立N+2或四个状态列。第一列是初始的伪观察值，第二列代表第一个观察音子[n]，第三列代表[iy]，第四列代表最后的伪观察值。开始时，在第一列中置开始状态的概率为为1.0，置其他概率为0；读者可以参看图5.20。为便于阅读，概率为0的单元都简单地用空白表示。

然后，正如在向前算法中那样，我们转移到下一个状态。对于列0中的每个状态，计算转移到列1中的每个状态的概率。取引导入当前单元的所有路径的延伸中最大的值为viterbi[t,j]的值。在时刻t-1从状态i出发的一条路径的延伸，只要把在向前算法中使用的三个因素相乘即可计算得到：