viterbi 算法是一个特殊但应用最广的动态规划算法，利用动态规划，可以解决任何一个图中的最短路径问题。而 viterbi 算法针对的是一个特殊的图 —— 篱笆网络的有向图（Lattice）的最短路径问题而提出的。它之所以重要，是因为凡是使用隐马尔可夫模型描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等
篱笆网络有向图的特点是同一列节点有多个，并且和上一列节点交错的连接起来。同一列节点代表同一个时间点上不同的状态的排列。说的直白点类似于神经网络
下面举一个比较简单的例子做说明：求 S 到 E 的最短路径，如下图
首先，我们假设 S 到 E 之前存在一条最短路径（红色），且这条路径经过 C2 点，那么我们便一定能确定从 S 到 C2 的 64 条（4X4X4=64）子路径当中 ，该子路径一定最短。（证明：反证法。如果 S 到 C2 之间存在一条更短的子路径，那么便可以用它来代替原先的路径，而原先的路径显然就不是最短了，这与原假设自相矛盾）
同理，我们也可以得出从 S 到 B2 点为两点间最短子路径的结论。既然如此，我们计算从 S 点出发到点 C2 的最短路径，是不是只要考虑从 S 出发到 B 层所有节点的最短路径就可以了？答案是肯定的！因为，从 S 到 E 的 "全局最短" 路径必定经过在这些 "局部最短" 子路径。
下面给出公式，设 $f (i)$ 为 $S$ 到节点 $i$ 的最短路径的值，$\text {dist}(i,j)$ 表示节点 $i$ 到节点 $j$ 的距离。则
$$ f(E)=\min(f(i)+\text{dist}(i,E)),\ \ \ i=A_1,A_2,...,C_4 $$
伪代码如下：
- f[1]=0
- pre[1] = 0 # pre[i]=j表示最短路径的路程中，由j跳转到i
- for i in range(point_num): # 遍历所有的点
- for j in incominglist: # 遍历所有指向这个点的路径
- best_score = inf
- score = f[j] + dist(j, i)
- if score < best_score:
- best_score = score
- pre[i] = j
