text: 最短路徑快速演算法，國際上一般認為是帶有佇列最佳化的Bellman-Ford 演算法，一般僅在中國大陸被稱為SPFA，是一個用於求解有向帶權圖單源最短路徑的演算法。這一演算法在隨機的稀疏圖上表現出色，並且適用於帶有負邊權的圖。 然而SPFA在最壞情況的時間複雜度與 Bellman-Ford 演算法相同，因此在非負邊權的圖中使用堆最佳化的Dijkstra 演算法效率可能優於SPFA。 SPFA演算法首先在1959年由作為廣度優先搜尋的擴充套件發表，相同演算法在1994年由段凡丁重新發現。演算法.給定一個有向帶權圖formula_1和一個源點formula_2，SPFA演算法可以計算從formula_2到圖中每個節點formula_4的最短路徑。其基本思路與 Bellman-Ford 演算法相同，即每個節點都被用作用於鬆弛其相鄰節點的備選節點。但相較於 Bellman-Ford 演算法，SPFA演算法的先進之處在於它並不盲目地嘗試所有節點，而是維護一個備選的節點佇列，並且僅有節點被鬆弛後才會將其放入佇列中。整個流程不斷重複，直至沒有節點可以被鬆弛。下面是這個演算法的虛擬碼。這裡的formula_5是一個備選節點的先進先出佇列，formula_6 是邊formula_7的權值。procedure Shortest-Path-Faster-Algorithm("G", "s")1 for each vertex "v" ≠ "s" in "V"("G")2 d("v") := ∞3 d("s") := 04 offer "s" into "Q"5 while "Q" is not empty6 "u" := poll "Q"7 for each edge ("u", "v") in "E"("G")8 if d("u") + w("u", "v")  "x""u" := pop front of "Q"push "u" to back of "Q"
metadata: erhwenkuo/wikipedia-zhtw
metadata: 最短路徑快速演算法
metadata: https://zh.wikipedia.org/wiki?curid=6162443