Shortest Path Faster Algorithm (SPFA) ???
最短路徑演算法，可分為兩大類別：Label Setting Algorithm 和 Label Correcting Algorithm。所謂 Label，就是在圖上的點（或邊）標記數值或符號，點擊這裡有 Label 的解釋。
歸類為 Label Setting Algorithm 的最短路徑演算法，是逐步設定每個點的最短路徑值，一旦設定後就不再更改。CLRS 上面記載的 Dijkstra’s Algorithm 即屬此類。
歸類為 Label Correcting Algorithm 的最短路徑演算法，則是設定某個點的最短路徑值之後，之後仍可繼續修正其值，越修越美。CLRS 上面記載的 Bellman-Ford Algorithm 和 Floyd-Warshall 皆屬此類。
以下全是我個人感想。SPFA，用來算單源最短路徑，是歸類為 Label Correcting Algorithm 的最短路徑演算法，點擊這裡是 SPFA 的演算法內容。說穿了 SPFA 並沒有什麼特別之處，就是拿 Label Correcting Algorithm 的概念算單源最短路徑，隨便用個容器把剛修正過的點暫存起來，以便後續修正。
SPFA 的概念我想數十年前老早就有了，只是沒有人為它起個名字，僅是簡單稱這是一個用了容器的 Label Correcting Algorithm。直到最近幾年，對岸有個膽子夠大的傢伙，自己把它取了個名字叫做 SPFA，從此之後中文網路上就開始有人用這名詞了，然而期刊論文上從來就沒有出現過 SPFA 這名詞。另外還有人稱 SPFA 是 Bellman-Ford Algorithm 的改良版，或是將 Dijkstra’s Algorithm + Binary Heap 稱之為 SPFA 優化，那又是更匪夷所思的一件事了。
我想大多數的人，包括我自己，都是由 CLRS 這本書開始學演算法的，自然是沒有聽過 Label Setting Algorithm 和 Label Correcting Algorithm 這兩個東西了。然而，它們其實是沿用已久的名詞、流傳已久的概念了，除了最短路徑演算法之外，也在別的地方被廣泛使用。如果大家先學會了 Label Correcting Algorithm，我想大家只會把 SPFA 當作是一種極單純的實作而已。
最後來論效率。判斷圖上有沒有負環，Bellman-Ford Algorithm 和 SPFA 那個快？結論是：SPFA 通常比較快，SPFA 輔以 Binary Heap 可能會更快。因為 SPFA 很容易就演變成一路往前衝，也就容易遇到一個負環；Bellman-Ford Algorithm 則是慢慢的讓每個點同時走一步，故不可能一早就生成長一點的負環。
求圖上可以有負邊的單源最短路徑樹，Bellman-Ford Algorithm 和 SPFA 那個快？這裡直接下個結論：SPFA 一定比 Bellman-Ford Algorithm 快。當圖上不存在負環的情況下，Bellman-Ford Algorithm 必須讓每個節點都設值 V-1 次，可是 SPFA 每個點最多就是 V-1 次了。當圖上有負環的情況下，Bellman-Ford 則必須讓所有節點都先設值 V-1 次之後，再讓各點設值 1 次到 0 次，才能確定有負環，結束演算法；SPFA 只要發現有某一個節點設值 V 次，即可確定有負環，馬上結束演算法。若把時間複雜度記為 O(kE)，Bellman-Ford Algorithm 的 k = V，SPFA 的 k <= V。當給定的圖是有向樹的時候，SPFA 可達到 k = 1，也是 SPFA 最快的極限了。當給定的圖是無向樹的時候，SPFA 可達到 k = 2。
SPFA 輔以 Priority Queue，效率通常會比普通的 SPFA 更好。用 Pirority Queue 通常可以更快地把節點的值，修正至真正的最短路徑值，少走很多冤枉路。當運氣非常好，SPFA + Priority Queue 執行過程跟 Label Setting 沒兩樣的時候，此時是 k = 1，但還要加上維護 Priority Queue 的時間。另外它也有運氣不好的時候，這裡提供一個例子：給定一張有向圖，起點在節點 1，邊 (1,2) (2,3) … (999,1000) 的權重都是 1，再讓邊 (1,1001) 的權重為 100，邊 (1001,2) 的權重為 -101，可以發現 SPFA + Prioirity Queue 會先從節點 1 一直衝到節點 1000，才會去走邊 (1,1001)。如果此時我們再加上邊 (1,1002) 其權重為 200，邊 (1002, 2) 其權重為 -202，那 SPFA + Priority Queue 又會走更多冤枉路了。
這裡再討論另外一種情況：CLRS 的習題中有提供一個讓 Bellman-Ford Algorithm 的 k 降至 V/2 的改進方法，改進之後，SPFA 就不一定會勝了。而 SPFA + Priority Queue 儘管很快，加上維護 Priority Queue 的時間，也許會勝也許不會勝。
求圖上所有邊皆為正權的單源最短路徑樹，Dijkstra’s Algorithm 和 SPFA 哪個快？結論是：Dijkstra’s Algorithm 極大多數的情況下都比 SPFA 快。大抵來說呢，Dijkstra’s Algorithm 一個節點僅設值一次，SPFA 一個節點至少設值一次，誰快誰慢由此可見一斑。然而 Dijkstra’s Algorithm 每次必須花 O(V) 時間從陣列找一個最小值，然後才能進行鬆弛操作，而 SPFA 則不需找最小值就可進行鬆弛操作，以這方面來看 SPFA 會快那麼一點。現在來討論看看：SPFA 會因為這麼一點點優點而勝出嗎？Dijkstra’s Algorithm 找最小值總共需時 O(V^2)，鬆弛操作總共需時 O(V+E) ，總共的時間複雜度是 O((V^2) + (V+E)) = O(V^2)。SPFA 的時間複雜度是 O(k1*d1 + k2*d2 + … + kv*dv)，其中 ki 是節點 i 被修正的次數，di 是節點 i 的出邊數，乘上 di 是指節點 i 被選取後進行鬆弛操作。以此概念來分析兩者優劣，只有當給定的圖非常稀疏，或者最短路徑樹和 BFS 樹長得很相像時，SPFA 才會有機會比 Dijkstra’s Algorithm 快上一些，其餘皆是 Dijkstra’s Algorithm 大勝。
這裡再討論另外一種情況：如果 Dijkstra’s Algorithm 和 SPFA 同時使用了 Priority Queue，則是變成了同一個演算法，既然一模一樣，就沒什麼好比。各位可以想想，SFPA 使用 Priority Queue 之後，求圖上所有邊皆為正權的單源最短路徑樹，其實就不再是 Label Correcting，變成是 Label Setting，那跟 Dijkstra’s Algorithm 其實就是同一件事。
最新留言