最短路徑快速算法
最短路徑快速算法(英語:Shortest Path Faster Algorithm (SPFA)),國際上一般認為是帶有隊列優化的Bellman-Ford 算法,一般僅在中國大陸被稱為SPFA,是一個用於求解有向帶權圖單源最短路徑的算法。這一算法在隨機的稀疏圖上表現出色,並且適用於帶有負邊權的圖。[1] 然而SPFA在最壞情況的時間複雜度與 Bellman-Ford 算法相同,因此在非負邊權的圖中使用堆優化的Dijkstra 算法效率可能優於SPFA。[2] SPFA算法首先在1959年由Edward F. Moore作為廣度優先搜索的擴展發表[3],相同算法在1994年由段凡丁重新發現。[4]
算法
給定一個有向帶權圖 和一個源點 ,SPFA算法可以計算從 到圖中每個節點 的最短路徑。其基本思路與 Bellman-Ford 算法相同,即每個節點都被用作用於鬆弛其相鄰節點的備選節點。但相較於 Bellman-Ford 算法,SPFA算法的先進之處在於它並不盲目地嘗試所有節點,而是維護一個備選的節點隊列,並且僅有節點被鬆弛後才會將其放入隊列中。整個流程不斷重複,直至沒有節點可以被鬆弛。
下面是這個算法的偽代碼。[5]這裡的 是一個備選節點的先進先出隊列, 是邊 的權值。
procedure Shortest-Path-Faster-Algorithm(G, s) 1 for each vertex v ≠ s in V(G) 2 d(v) := ∞ 3 d(s) := 0 4 offer s into Q 5 while Q is not empty 6 u := poll Q 7 for each edge (u, v) in E(G) 8 if d(u) + w(u, v) < d(v) then 9 d(v) := d(u) + w(u, v) 10 if v is not in Q then 11 offer v into Q
對於無向圖,將每條無向邊視作兩條有向邊以採用 SPFA 算法。
最壞情況下的性能
下面是一種觸發該算法低性能表現的數據構造方式。假設要求從節點1到節點 的最短路徑。對於整數 ,考慮添加邊 並令其權為一個隨機的小數字(於是最短路應為1-2-...- ),同時隨機添加 條其他的權較大的邊。在這種情況下,SPFA算法的性能表現將會非常低下。[1]
SPFA算法本質上依然被認為是Bellman-Ford算法的一個特例,因此一般認為SPFA算法的最差複雜度是 ,其中 為點數, 為邊數。[1]
NOI2018中,出題人使用特殊構造圖卡到SPFA算法的最壞情況,並在講題時在幻燈片上打出關於「SPFA它死了」的字樣,導致現今很多中國大陸OI題目都會構造特殊數據卡掉SPFA,於是關於SPFA已死的說法廣泛流傳於中國大陸。[原創研究?]
優化技巧
SPFA算法的性能很大程度上取決於用於鬆弛其他節點的備選節點的順序。事實上,如果 是一個優先隊列,則這個算法將很類似於Dijkstra 算法。然而儘管這一算法中並沒有用到優先隊列,仍有多種可用的技巧可以用來提升隊列的質量,藉此能夠提高平均性能(但仍無法提高最壞情況下的性能)。其中,最著名的兩種技巧通過重新調整 中元素的順序從而使得更靠近源點的節點能夠被更早地處理。因此一旦實現了這兩種技巧, 將不再是一個先進先出隊列,而更像一個鍊表或雙端隊列。
距離小者優先 (Small Label First(SLF))(由Bertsekas在Networks, 第23期, 1993, P703-P709中最先提出)。在偽代碼的第十一行,將總是把 壓入隊列尾端修改為比較 和 ,並且在 較小時將 壓入隊列的頭端。這一技巧的偽代碼如下(這部分代碼插入在上面的偽代碼的第十一行後):
procedure Small-Label-First(G, Q) if d(back(Q)) < d(front(Q)) then u := pop back of Q push u into front of Q
距離大者置後 (Large Label Last(LLL))(由Bertsekas、Guerriero、與Musmanno在JOTA, 第88期, 1996, 頁297-320最先提出)。在偽代碼的第十一行,我們更新隊列以確保隊列頭端的節點的距離總小於平均,並且任何距離大於平均的節點都將被移到隊列尾端。偽代碼如下:
procedure Large-Label-Last(G, Q) x := average of d(v) for all v in Q while d(front(Q)) > x u := pop front of Q push u to back of Q
參考文獻
- ^ 1.0 1.1 1.2 About the so-called SPFA algorithm. [2018-05-25]. (原始內容存檔於2020-11-17).
- ^ SPFA算法 (頁面存檔備份,存於網際網路檔案館)
- ^ Moore, Edward F. Proceedings of the International Symposium on the Theory of Switching. Harvard University Press: 285–292. 1959.
|contribution=
被忽略 (幫助) SPFA is Moore's 「Algorithm D」. - ^ Duan, Fanding, 关于最短路径的SPFA快速算法, 西南交通大學學報 [Journal of Southwest Jiaotong University], 1994, 29 (2): 207–212 [2018-05-25], (原始內容存檔於2019-04-25)
- ^ 存档副本. [2018-05-25]. (原始內容存檔於2021-01-16).
擴展閱讀
- 夏正冬; 卜天明; 張居陽. SPFA算法的分析及改进. 《計算機科學》. 2014, 41 (6): 180–184 [2020-11-17]. (原始內容存檔於2020-12-08).