SPFA

• 本質：DP，基于隊列優化的Bellman-Ford

• 特點：單源最短路，求解一個源點到其他所有點的最短距離，不穩定

• 適用對象：允許負權圖，不允許負環圖(負環：圖上邊權之和為負的環，負環圖無法求解最短路)，同時也可求最長路。

• 存儲結構：鏈式前向星

• 核心思想：用隊列保存松弛邊的出度點，調整其鄰接點

• 優化思路：進行松弛操作的的鄰接點入隊

• 算法流程：閆氏DP分析法

  • 狀態表示：

    • 集合：設源點$S$，當前輪起點(非源點)為$U$，當前輪起點鄰接點$V$。定義源點$S$到每個頂點的最短路長度$dis$(初始化為$+\infty$表示該點不可達，源點初始化為0)，路徑數組$path$(存儲其上一個來源頂點,初始化為$?1$表示無路徑)，待處理點隊列$Q$(用于維護被松弛邊的鄰接點)，頂點隊列狀態標記數組$in$，頂點入隊次數數組$cnt$。
    • 屬性：$Min$

  • 狀態計算：

    • 不選第$k$條邊：若選當前邊不能使邊的終點$V$到源點$S$的距離減小，則不選該邊。$dis[V]$不變。
    • 選第$k$條邊：若選當前邊能夠使邊的終點$V$到源點$S$的距離減小，則選該邊。$dis[V]=dis[U]+W$。(該邊被松弛，之后的調整發生在該邊終點及其一系列鄰接點上，若該終點不在隊列中，則將其入隊)

  • 狀態轉移方程式：$dis[V]=min(dis[V],dis[U]+W)$

• 復雜度：一般為$O(E)$，最差情況下退化至$O(VE)$
  由于SPFA的不穩定性，因此可構造數據使SPFA超時。若求解非負權圖的最短路，應優先選用Dijkstra

實現

void spfa(){
	vector<int>dis(n+1,INF),path(n+1,-1),cnt(n+1);
    vector<bool>in(n+1);//標記數組,用于判斷頂點是否在隊列中
	queue<int>q;//松弛后待處理頂點隊列
    dis[s]=0,q.push(s),in[s]=1,cnt[s]=1;
    while(q.size()){
        int U=q.front();
        q.pop(),in[U]=0;//注意一定要彈出U,否則會使U在當前輪無法重新入隊
        for(int i=v[U].e;~i;i=e[i].n){//~i:i!=-1
            int V=e[i].v,W=e[i].w;
            if(dis[U]!=INF&&W!=INF&&dis[V]>dis[U]+W){
                //松弛3個條件:當前起點dis非無窮,邊權值非無窮,當前鄰接點通過當前起點中轉dis更小
                dis[V]=dis[U]+W,path[V]=U;
                if(!in[V])//該邊終點不在隊列中,將其入隊
                    q.push(V),in[V]=1,cnt[V]++;
            }
        }
    }
}

判斷負環

若任意一點$cnt>n$，則說明存在負環

bool check(){
    for(auto i:cnt)
        if(i>n) return 1;
    return 0;
}

應用：差分約束系統

給定$n$元一元一次不等式組，$n$個變量$x_1$~$x_n$，$m$個形如$x_i?x_j\le c_k$的兩變量之差的約束條件($c_k$為任意常數)，求滿足約束條件的一組可行解。

解的情況：無解/無窮解(帶有任意常數仍成立)

轉換為最短路：不等式可轉換為$x_i\le x_j+c_k$，與最短路松弛操作完全一致。因此可將$x_i$看作節點$v$，$x_j$看作節點$u$，每個約束條件即為$<j,i>$。

算法流程：

• 增設虛擬源點$s$，并在$s$與其他各點增設一條$w=0$的邊
• 處理約束條件，將不等式轉換為有向邊

不等式	變形式	加邊操作
$x_i?x_j\le c_k$	$x_i\le x_j+c_k$	$add(j,i,c_k)$
$x_i?x_j\ge c_k$	$x_j\le x_i?c_k$	$add(i,j,?c_k)$
$x_i?x_j=c_k$	$x_i?x_j\le c_k,x_i?x_j\ge c_k$	$add(j,i,c_k),add(i,j,?c_k)$

• 運行SPFA。若出現負環則無解；否則$dis[i]$為則$x_i$的一組可行解。

應用：最長路

存邊時，邊權存相反數。運行SPFA，最終的$dis$再取相反數，則為最長路。