SPFA算法，全稱為Shortest Path Faster Algorithm，是求解單源最短路徑問(wèn)題的一種常用算法，它可以處理有向圖或者無(wú)向圖，邊權(quán)可以是正數(shù)、負(fù)數(shù)，但是不能有負(fù)環(huán)。

1. 初始化

首先我們需要起點(diǎn)s到其他頂點(diǎn)的距離初始化為一個(gè)很大的值（比如9999999，像是 JAVA 中可以設(shè)置 Integer.MAX_VALUE 來(lái)使），并將起點(diǎn)s的距離初始化為0。同時(shí)，我們還需要將起點(diǎn)s入隊(duì)。

2. 迭代

每次從隊(duì)列中取出一個(gè)頂點(diǎn)u，遍歷所有從u出發(fā)的邊，對(duì)于邊（u,v）（其中v為從u可以到達(dá)的頂點(diǎn)），如果s->u->v的路徑長(zhǎng)度小于s->v的路徑長(zhǎng)度，那么我們就更新s->v的路徑長(zhǎng)度，并將v入隊(duì)。

3. 循環(huán)

不斷進(jìn)行步驟2，直到隊(duì)列為空。

4. 判斷

最后，我們可以得到從起點(diǎn)s到各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度，如果存在無(wú)窮小的距離，則說(shuō)明從起點(diǎn)s無(wú)法到達(dá)該頂點(diǎn)。

需要注意的是，在每次迭代中，只有當(dāng)前連通塊中的頂點(diǎn)會(huì)被更新，因此SPFA算法的時(shí)間復(fù)雜度為O(VE+V^2),其中V是頂點(diǎn)數(shù)，E是邊數(shù)。