边权重
知乎上有个相关的提问，高赞回答说，Viterbi算法的优势是能够处理带节点权重问题。无论是Viterbi算法，还是Dijsktra算法，处理的都是边上的权重，不涉及节点的权重。
用李航老师《统计学习方法》第186页中的HMM+Viterbi例子来分析。
从上图可以看到，Viterbi算法处理的也是边权重的最优路径问题。
最优路径与最短路径
注意，上文一直说最优路径，而不是最短路径。这是因为Viterbi算法不仅仅可以求最短路径，它还可以求最长路径，或者是最小乘积路径，或者最大乘积路径。
为什么Viterbi算法可以求解最长路径呢？因为Viterbi算法是动态规划算法。它首先求出到达A子节点的最长路径。因为经过B的最长路径必然包括经过A的最长路径，因此可以基于A，找到到达B的最长路径。同理，可以找到C，D，E...的最长路径，直至最终节点。
最大似然概率，通过取负对数求和，可以转化为最短路径问题。Dijsktra算法要求路径长度为非负数。因此，取负对数之前，每条边应该。由于概率值必然满足此条件，因此最大似然概率可以转化为最短路径问题，并用Dijsktra算法求解。
如果边长大于1，取负对数后长度为负数。此时依旧可以用Viterbi算法，但是Dijsktra算法用不了。
假设边长大于0，两个算法的适用范围及条件为：
| 算法 | 最大乘积 | 最小乘积 | 最短路径 | 最长路径 |
|---|---|---|---|---|
| Dijsktra | 当边长<=1时，取负对数转化为最短路径 | 不可以 | 可以 | 不可以 |
| Viterbi | 可以 | 可以 | 可以 | 可以 |
下面是最大似然概率取负对数后，转化为最短路径问题的示意图。
Dijsktra与Viterbi
Dijsktra算法属于贪心算法，Viterbi算法属于动态规划算法。从另一个角度来看，Dijsktra算法是深度优先图算法，Viterbi算法则是广度优先图算法。
以上图为例，要寻找A1-> D1的最短路径，Dijsktra算法依次考察：A1, (B1, B2), C1, D1, C2, D1(第二次)。
而Viterbi算法按离起始点的距离迭代。以上图为例，Viterbi算法依次考察：A1, (B1, B2), (C1, C2), D1。离起始点距离越远，迭代次序越靠后。
Viterbi算法的优势
对于HMM模型，无论是Dijsktra算法，还是Viterbi算法，都能够求出最优序列。那么为什么HMM算法一般使用Viterbi算法，而不是Dijsktra算法？
我认为Viterbi算法的优势在于速度。
假设模型共有L步，每一步有N个隐状态。从t时刻到t+1时刻，Viterbi算法需要进行次加法和比较操作。考虑到共有L步，因此Viterbi算法耗时
Dijsktra算法的时间复杂度分析可以参考《算法导论》关于Dijsktra算法一节。这里直接用结论，如果不使用斐波那契堆，Dijsktra算法的复杂度为。其中
，因此，复杂度为
Viterbi算法的劣势
我们通过下图来观察Viterbi算法的劣势：
用Viterbi算法计算，通过三条路径，T1距离起点分别为2，3，6。因此T1会在第2，3，6轮迭代进行比较，更新。且T1之后所有的点，都会在第k+2, K+3, K+6次迭代中重复更新。
当存在点，它有多条路径通向起点，且长度不一时，Viterbi算法存在大量的重复计算。
在机器学习中，Viterbi算法一般用于序列解码。这是因为序列中每个时刻，它的状态点离起始点的距离都是一样的。这种情况下不存在重复计算问题。
总结
综上，无论是Viterbi算法，还是Dijsktra算法，都是处理边权重图的最优路径问题。
Viterbi算法既可以处理最大/最小乘法问题，也可以处理最大/最小加法问题。而Dijsktra算法只能够处理最小加法问题，或者将大于0，小于1的乘法问题转化为最小加法（最短路径）问题。
Viterbi算法属于动态规划算法，Dijsktra算法属于贪心算法。Viterbi算法是广度优先，Dijsktra算法是深度优先。
HMM，CRF等算法中使用Viterbi算法，是因为Viterbi算法的效率比Dijsktra算法高。
当图中存在点，它有多条路径通往起始点，且路径长度不一样时，Viterbi算法存在重复计算问题。此时用Dijsktra算法效率更高。
