最短路徑快速算法(英語:Shortest Path Faster Algorithm , SPFA))是一個用於求解有向帶權圖單源最短路徑的改良的貝爾曼-福特算法。這一算法被認為在隨機的稀疏圖上表現出色,並且極其適合帶有負邊權的圖。然而SPFA在最壞情況的時間複雜度與貝爾曼-福特算法相同,因此在非負邊權的圖中仍然最好使用戴克斯特拉算法。SPFA算法是在1994年由段凡丁發表的。
基本介紹
- 中文名:最短路徑快速算法
- 外文名:Shortest Path Faster Algorithm,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
性能
平均情況下的性能
最壞情況下的性能
最佳化技巧
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
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