viterbi演算法和Dijkstra演算法的演算法思想是否相同？
請教一下，viterbi演算法和Dijkstra演算法在演算法思想本質上是不是相同的？
兩種演算法都是從起始點出發，尋找當前結點到下一結點的最短路徑並存儲，同時用於迭代到再下一個結點的最短路徑。
兩種演算法在計算DAG的最短路徑時都可以找到最優解，但有種情況例外
Dijkstra是貪心的，在解決節點有額外權重問題的可能找不到最優解
拿《統計學習方法》186頁的一個例題來說：
用viterbi算出來的最大概率路徑為（3，3，3），而用dijkstra求解的話，t=1時選擇3節點沒毛病，如果只看狀態轉移矩陣，是P(t=2,i=3|t=1,i=3)=0.5最大，但是要考慮到節點權重（觀測矩陣）的話，在t=2時從3節點轉移到2節點的路徑概率是最大的（0.0504），因此在節點有額外的權重時會陷入局部最優。
邊權重
反對李如說，「Viterbi演算法的優勢是能夠處理帶節點權重問題」。無論是Viterbi演算法，還是Dijsktra演算法，處理的都是邊上的權重，不涉及節點的權重。
用李航老師《統計學習方法》第186頁中的HMM+Viterbi例子來分析。
這個例子可以轉化為求解下圖的最優路徑。其中從start -&> A是觀測矩陣 * 發射矩陣。A -&> B, B -&> C是狀態轉移矩陣 * 發射矩陣（為了節約空間省去了部分連線）
從上圖可以看到，Viterbi演算法處理的也是邊權重的最優路徑問題。
最優路徑與最短路徑
注意，上文一直說最優路徑，而不是最短路徑。這是因為Viterbi演算法不僅僅可以求最短路徑，它還可以求最長路徑，或者是最小乘積路徑，或者最大乘積路徑。
為什麼Viterbi演算法可以求解最長路徑呢？因為Viterbi演算法是動態規劃演算法。它首先求出到達A子節點的最長路徑。因為經過B的最長路徑必然包括經過A的最長路徑，因此可以基於A，找到到達B的最長路徑。同理，可以找到C，D，E...的最長路徑，直至最終節點。
最大似然概率，通過取負對數求和，可以轉化為最短路徑問題。Dijsktra演算法要求路徑長度為非負數。因此，取負對數之前，每條邊應該$0 &< value &<= 1$。由於概率值必然滿足此條件，因此最大似然概率可以轉化為最短路徑問題，並用Dijsktra演算法求解。
如果邊長大於1，取負對數後長度為負數。此時依舊可以用Viterbi演算法，但是Dijsktra演算法用不了。
假設邊長大於0，兩個演算法的適用範圍及條件為：
下面是最大似然概率取負對數後，轉化為最短路徑問題的示意圖。
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演算法效率更高。
維特比只能用於有向無環圖求最長最短路徑，因為有環的時候 維特比的動態規劃的遞推公式會相互依賴形成類似於死鎖的結構，沒法解出來
Dijkstra 都可以（有向五環，有向有環，無向圖），但要求 權重不能為負值
Floyd 演算法都可以（有向五環，有向有環，無向圖，權重可以為負值）
一點粗淺的心得：
維特比演算法是一種動態規劃。首先，找到t時刻下，到達該時刻中N個結點的最短子路徑(因為是到達N個結點的最短子路徑，因此這時的最短子路徑有N條，還不是唯一的)。
到t+1時刻，假設有M個結點，就在t時刻找出的N條最短子路徑的基礎上，找到t+1時刻到達M個結點的M條最短子路徑。依此類推。
在倒數第二個時刻，假設有X個結點，則此時規劃出來的最短子路徑還有X條。
但到了最後時刻，在X條最短子路徑裏，其中只有1條能延伸成為最終全局最短(或概率最大)的路徑。最後回溯這條最短路徑經歷的各結點。完成演算法。
總的來看，viterbi作為一種動態規劃演算法，每個子部分只存儲最優子路徑，而不是窮盡地枚舉所有起點到終點的路徑來獲得最優路徑。
viterbi與Dijkstra的區別——
(1)前者是動態規劃，後者是貪心演算法。這是前一位答主Hengkai guo也提及的。
(2)前者能夠達到全局最優；而後者不一定。如前所述，Viterbi存儲了到達倒數第二個時刻下X個結點的X條最短子路徑，這是它達到全局最優的保證。
而Dijkstra演算法在t,t+1,……每個時刻都選局部最優，在倒數第二個時刻也只保留了一條最短子路徑，最後反而不一定能達到全局最優(有可能最後一段路非常的長)。
前者是動態規劃，後者是貪心。只不過都是分階段而已。
Viterbi演算法可以解決多起始點的、且節點有額外權重的問題，Dijkastra不行。
推薦閱讀：
