-
最短路徑快速算法
鎖定
- 中文名
- 最短路徑快速算法
- 外文名
- Shortest Path Faster Algorithm,SPFA
最短路徑快速算法算法
SPFA算法的基本思路與貝爾曼-福特算法相同，即每個節點都被用作用於鬆弛其相鄰節點的備選節點。相較於貝爾曼-福特算法，SPFA算法的提升在於它並不盲目嘗試所有節點，而是維護一個備選節點隊列，並且僅有節點被鬆弛後才會放入隊列中。整個流程不斷重複直至沒有節點可以被鬆弛。
下面是這個算法的偽代碼。這裏的
是一個備選節點的先進先出隊列，
是邊
的權。
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
這個算法也可以通過將每條邊換為兩條逆向的邊來用於無向圖。
最短路徑快速算法性能
最短路徑快速算法平均情況下的性能
一般情況下，對於一張隨機圖，基於實驗獲得的平均時間複雜度為
。
最短路徑快速算法最壞情況下的性能
下面是一種觸發該算法低性能表現的數據構造方式。假設要求從節點1到節點
的最短路徑。對於整數
，考慮添加邊
並令其權為一個隨機的小數字（於是最短路應為1-2-...-
），同時隨機添加
條其他的權較大的邊。在這種情況下，SPFA算法的性能表現將會非常低下。
最短路徑快速算法優化技巧
SPFA算法的性能很大程度上取決於用於鬆弛其他節點的備選節點的順序。事實上，如果
是一個優先隊列，則這個算法將極其類似於戴克斯特拉算法。然而儘管這一算法中並沒有用到優先隊列，仍有兩種可用的技巧可以用來提升隊列的質量，並且藉此能夠提高平均性能（但仍無法提高最壞情況下的性能）。兩種技巧通過重新調整
中元素的順序從而使得更靠近源點的節點能夠被更早地處理。因此一旦實現了這兩種技巧，
將不再是一個先進先出隊列，而更像一個鏈表或雙端隊列。
距離小者優先 （Small Label First，SLF)，在偽代碼的第十一行，將總是把
壓入隊列尾端修改為比較
和
，並且在
較小時將
壓入隊列的頭端。這一技巧的偽代碼如下（這部分代碼插入在上面的偽代碼的第十一行後）：
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)，在偽代碼的第十一行，我們更新隊列以確保隊列頭端的節點的距離總小於平均，並且任何距離大於平均的節點都將被移到隊列尾端。偽代碼如下：
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. 關於最短路徑的SPFA快算法 ．百度學術[引用日期2018-07-20]
