最短路徑快速算法

維基百科,自由的百科全書
跳至導覽 跳至搜尋

最短路徑快速算法英語:Shortest Path Faster Algorithm (SPFA))是一個用於求解有向帶權圖單源最短路徑的改良的貝爾曼-福特算法。這一算法被認為在隨機的稀疏圖上表現出色,並且極其適合帶有負邊權的圖。[1] 然而SPFA在最壞情況的時間複雜度與貝爾曼-福特算法相同,因此在非負邊權的圖中仍然最好使用戴克斯特拉算法[2] SPFA算法是在1994年由段凡丁發表的。[3]

算法[編輯]

本算法沒有經過證明的平均時間複雜度。

給定一個有向帶權圖和一個源點,SPFA算法計算從到圖中每個節點的最短路徑。對於每個節點,從 的最短路徑表示為

SPFA算法的基本思路與貝爾曼-福特算法相同,即每個節點都被用作用於鬆弛其相鄰節點的備選節點。相較于貝爾曼-福特算法,SPFA算法的提升在於它並不盲目嘗試所有節點,而是維護一個備選節點隊列,並且僅有節點被鬆弛後才會放入隊列中。整個流程不斷重複直至沒有節點可以被鬆弛。

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

一個基於歐氏幾何距離的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

這個算法也可以通過將每條邊換為兩條逆向的邊來用於無向圖。

正確性證明[編輯]

http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm

平均情況下的性能[編輯]

對於一張隨機圖,基於實驗獲得的平均時間複雜度為[3]

最壞情況下的性能[編輯]

下面是一種觸發該算法低性能表現的數據構造方式(沒有隊列優化?)。[1]假設要求從節點1到節點的最短路徑。對於整數,考慮添加邊並令其權為一個隨機的小數字(於是最短路應為1-2-...-),同時隨機添加條其他的權較大的邊。在這種情況下,SPFA算法的性能表現將會非常低下。

優化技巧[編輯]

SPFA算法的性能很大程度上取決於用於鬆弛其他節點的備選節點的順序。事實上,如果是一個優先隊列,則這個算法將極其類似於戴克斯特拉算法。然而儘管這一算法中並沒有用到優先隊列,仍有兩種可用的技巧可以用來提升隊列的質量,並且藉此能夠提高平均性能(但仍無法提高最壞情況下的性能)。兩種技巧通過重新調整中元素的順序從而使得更靠近源點的節點能夠被更早地處理。因此一旦實現了這兩種技巧,將不再是一個先進先出隊列,而更像一個鍊表或雙端隊列。

距離小者優先Small Label First(SLF))(由Bertsekas在Networks, 第23期, 1993, 頁703-709中最先提出)。在偽代碼的第十一行,將總是把壓入隊列尾端修改為比較,並且在較小時將壓入隊列的頭端。這一技巧的偽代碼如下(這部分代碼插入在上面的偽代碼的第十一行後):

 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

參見[編輯]