跳至內容

最短路徑快速算法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

最短路徑快速算法(英語: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]

算法

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

下面是這個算法的偽代碼。[5]這裡的是一個備選節點的先進先出隊列, 是邊的權值。

一個基於歐氏幾何距離的SPFA算法。紅線是當前狀態下的各條最短路徑。藍線表示鬆弛發生的地方,也即通過在中用節點連接可以給出一條從源點到更短的路徑
 procedure Shortest-Path-Faster-Algorithm(G, s)
  1    for each vertex vs 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. ^ 1.0 1.1 1.2 About the so-called SPFA algorithm. [2018-05-25]. (原始內容存檔於2020-11-17). 
  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」.
  4. ^ Duan, Fanding, 关于最短路径的SPFA快速算法, 西南交通大學學報 [Journal of Southwest Jiaotong University], 1994, 29 (2): 207–212 [2018-05-25], (原始內容存檔於2019-04-25) 
  5. ^ 存档副本. [2018-05-25]. (原始內容存檔於2021-01-16). 

擴展閱讀