最短路徑快速演算法

最短路徑快速演算法（英語：Shortest Path Faster Algorithm (SPFA)），國際上一般認為是帶有佇列最佳化的Bellman-Ford 演算法，一般僅在中國大陸被稱為SPFA，是一個用於求解有向帶權圖單源最短路徑的演算法。這一演算法在隨機的稀疏圖上表現出色，並且適用於帶有負邊權的圖。^[1] 然而SPFA在最壞情況的時間複雜度與 Bellman-Ford 演算法相同，因此在非負邊權的圖中使用堆最佳化的Dijkstra 演算法效率可能優於SPFA。^[2] SPFA演算法首先在1959年由Edward F. Moore（英語：Edward F. Moore）作為廣度優先搜尋的擴充發表^[3]，相同演算法在1994年由段凡丁重新發現。^[4]

演算法

給定一個有向帶權圖 $G=(V,E)$ 和一個源點 $s$ ，SPFA演算法可以計算從 $s$ 到圖中每個節點 $v$ 的最短路徑。其基本思路與 Bellman-Ford 演算法相同，即每個節點都被用作用於鬆弛其相鄰節點的備選節點。但相較於 Bellman-Ford 演算法，SPFA演算法的先進之處在於它並不盲目地嘗試所有節點，而是維護一個備選的節點佇列，並且僅有節點被鬆弛後才會將其放入佇列中。整個流程不斷重複，直至沒有節點可以被鬆弛。

下面是這個演算法的虛擬碼。^[5]這裡的 $Q$ 是一個備選節點的先進先出佇列， $w(u,v)$ 是邊 $(u,v)$ 的權值。

一個基於歐氏幾何距離的SPFA演算法。紅線是當前狀態下的各條最短路徑。藍線表示鬆弛發生的地方，也即通過在 $Q$ 中用節點 $u$ 連接 $v$ 可以給出一條從源點到 $v$ 更短的路徑

 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到節點 $n$ 的最短路徑。對於整數 $1\leq i<n$ ，考慮添加邊 $(i,i+1)$ 並令其權為一個隨機的小數字（於是最短路應為1-2-...- $n$ ），同時隨機添加 $4n$ 條其他的權較大的邊。在這種情況下，SPFA演算法的效能表現將會非常低下。^[1]

SPFA演算法本質上依然被認為是Bellman-Ford演算法的一個特例，因此一般認為SPFA演算法的最差複雜度是 $O(|V|\cdot |E|)$ ，其中 $|V|$ 為點數， $|E|$ 為邊數。^[1]

NOI2018中，出題人使用特殊構造圖卡到SPFA演算法的最壞情況，並在講題時在幻燈片上打出關於「SPFA它死了」的字樣，導致現今很多中國大陸OI題目都會構造特殊資料卡掉SPFA，於是關於SPFA已死的說法廣泛流傳於中國大陸。^{[原創研究？]}

最佳化技巧

SPFA演算法的效能很大程度上取決於用於鬆弛其他節點的備選節點的順序。事實上，如果 $Q$ 是一個優先佇列，則這個演算法將很類似於Dijkstra 演算法。然而儘管這一演算法中並沒有用到優先佇列，仍有多種可用的技巧可以用來提升佇列的品質，藉此能夠提高平均效能（但仍無法提高最壞情況下的效能）。其中，最著名的兩種技巧通過重新調整 $Q$ 中元素的順序從而使得更靠近源點的節點能夠被更早地處理。因此一旦實現了這兩種技巧， $Q$ 將不再是一個先進先出佇列，而更像一個鏈結串列或雙端佇列。

距離小者優先 （Small Label First(SLF)）（由Bertsekas在Networks, 第23期, 1993, P703-P709中最先提出)。在虛擬碼的第十一行，將總是把 $v$ 壓入佇列尾端修改為比較 $d(v)$ 和 $d{\big (}{\text{front}}(Q){\big )}$ ，並且在 $d(v)$ 較小時將 $v$ 壓入佇列的頭端。這一技巧的虛擬碼如下（這部分代碼插入在上面的虛擬碼的第十一行後）：

 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）.

[poj-1] 1.0 ^1.1 ^1.2 About the so-called SPFA algorithm. [2018-05-25]. （原始內容存檔於2020-11-17）.

[nocow-2] SPFA演算法（頁面存檔備份，存於網際網路檔案館）

[3] 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-4] Duan, Fanding, 关于最短路径的SPFA快速算法, 西南交通大學學報 [Journal of Southwest Jiaotong University], 1994, 29 (2): 207–212 [2018-05-25], （原始內容存檔於2019-04-25）

[codeforce-5] 存档副本. [2018-05-25]. （原始內容存檔於2021-01-16）.

[1]

[2]

[3]

[4]

[5]