维特比算法

维特比算法用于计算从起点到终点的最短路径。
采用动态规划的方法，将起到到终点的距离计算,，划分为一个一个的小问题。
比如：计算A——>B（B1,B2,B3）——>C(C1,C2,C3)——>D(D1,D2,D3)——>E的最短距离。

1. 划分为A——>B——>C：1）A——>B（B1,B2,B3）——>C1，2）A——>B（B1,B2,B3）——>C2，3）A——>B（B1,B2,B3）——>C3。分别计算这三者的距离，得到A——>C(C1,C2,C3)的距离。复杂度：$2(加法计算)\times3\times3$2(加法计算)×3×3
2. 划分为A——>C——>D：1）A——>C（C1,C2,C3）——>D1，2）A——>C（C1,C2,C3）——>D2，3）A——>C（C1,C2,C3）——>D3。分别计算这三者的距离，得到A——>D(D1,D2,D3)的距离。复杂度：$2(加法计算)\times3\times3$2(加法计算)×3×3
3. A——>D（D1,D2,D3）——>E。复杂度：$2(加法计算)\times3$2(加法计算)×3

相邻两层间(A——B(m个节点)——C(n个节点))的计算复杂度为$2\times m \times n$2×m×n

算法的具体过程参考