❶ SPFASPFA演算法
SPFA演算法，全稱為Shortest Path Faster Algorithm，是由西南交通大學的段凡丁在1994年提出的一種求解單源最短路問題的有效演算法。該演算法在處理存在負權邊的圖時尤為適用，當Dijkstra等演算法失效，而Bellman-Ford演算法復雜度過高時，SPFA演算法就能發揮作用。
我們假設給定的有向加權圖G不存在負權迴路，這樣最短路徑的存在是確定的。雖然在執行前可以先通過拓撲排序檢查，但這不是演算法的核心。演算法的關鍵在於使用一個先進先出的隊列存儲待優化節點，每次從隊列頭部取出節點u，對離開u的所有鄰接節點v進行鬆弛操作。如果v的估計最短路徑值改變且不在隊列中，就將v加入隊尾。這個過程將持續，直到隊列為空。其原理是，只要最短路徑存在，SPFA演算法必然能找到最小值。
演算法的時間復雜度期望為O(ke)，其中k是所有頂點進隊的平均次數，一般小於等於2。具體實現是：初始化隊列和一個記錄最短路徑的表格，起始點的最短路徑值設為極大值（自身為0）。然後執行鬆弛操作，若更新路徑且未入隊，將該點加入隊尾，重復此過程直到隊列為空。通過節點進隊次數判斷是否存在負環：如果某個點超過n次進入隊列，說明存在負權迴路，此時無最短路徑，演算法將無限進行直到發現負環。
❷ SPFA演算法SPFA演算法
SPFA演算法，全稱為Shortest Path Faster Algorithm，是由西南交通大學段凡丁在1994年提出的一種求解單源最短路徑問題的高效演算法。在處理圖中存在負權邊的情況時，如Dijkstra演算法不再適用，Bellman-Ford演算法復雜度偏高，SPFA演算法就能派上用場。
演算法的核心原理是動態逼近法，利用一個先進先出的隊列存儲待優化的節點。通過鬆弛操作，以起點u的當前最短路徑估計值更新其鄰接節點v的值。若更新後v不在隊列中，將其加入隊尾。此過程持續直至隊列為空。該演算法確保只要有最短路徑存在，最終一定能找到最小值。
SPFA的期望時間復雜度為O(ke)，其中k是所有頂點平均入隊次數，通常k小於等於2。其基本實現包括創建隊列，初始時僅包含起點，以及一個記錄最短路徑的表格（初始值設為極大值，起點到本身的路徑設為0）。通過鬆弛操作不斷更新路徑，如果刷新成功且新加入的點不在隊列中，將其加入隊尾，直至隊列為空。
值得注意的是，SPFA演算法在判斷圖中是否存在負權環時，如果某個點入隊次數超過圖中節點總數N，說明存在負環，此時SPFA演算法無法處理帶負環的圖。