SPFA 算法詳解：求帶負權邊的單源最短路 (隊列優化 Bellman-Ford)

算法原理

SPFA (Shortest Path Faster Algorithm) 是 Bellman-Ford 的隊列優化版。僅將「被鬆弛」的節點入隊，避免無效掃描。適用於含負權邊、無負環的單源最短路。

核心流程

1. 初始化：dist[s]=0，其餘 INF；源點入隊，標記 inQueue
2. 隊列不空：取出 u，標記出隊
3. 遍歷 u 的出邊 (u,v,w)：若 dist[u]+w < dist[v] 鬆弛
4. 若 v 不在隊列：入隊，入隊次數++，超過 N 次說明有負環

標準實現模板

const int MAXN = 10005, MAXM = 500005;
int head[MAXN], to[MAXM], wgt[MAXM], nxt[MAXM], ecnt;
int dist[MAXN], cnt[MAXN]; bool inq[MAXN];

void addEdge(int u,int v,int w){
    to[ecnt]=v; wgt[ecnt]=w; nxt[ecnt]=head[u]; head[u]=ecnt++;
}

bool spfa(int s, int n){
    fill(dist, dist+n+1, INF);
    memset(cnt,0,sizeof(cnt)); memset(inq,0,sizeof(inq));
    queue q; q.push(s); dist[s]=0; inq[s]=true; cnt[s]=1;
    while(!q.empty()){
        int u=q.front(); q.pop(); inq[u]=false;
        for(int e=head[u]; ~e; e=nxt[e]){
            int v=to[e];
            if(dist[u]+wgt[e] < dist[v]){
                dist[v]=dist[u]+wgt[e];
                if(!inq[v]){
                    inq[v]=true;
                    if(++cnt[v] > n) return false; // 負環
                    q.push(v);
                }
            }
        }
    }
    return true;
}

關鍵優化 (SLF/LLL)

• SLF (Small Label First)：新入隊節點 dist < 隊首 dist 時插隊首
• LLL (Large Label Last)：隊首 dist > 平均 dist 時移至隊尾
• 實測可顯著減少鬆弛次數，防止最壞情況退化

避坑指南

• 邊存儲用鏈式前向星 (head/to/wgt/nxt) 而非 vector，效率更高
• 入隊次數統計 cnt[v] 必須在入隊時 ++，出隊不 --
• 負環判定：cnt[v] > N 而非 >= N
• 圖不連通時需加超級源點連向所有點 (權 0) 跑一次

參考資源

詳細證明與 DFS 版實現可參考：SPFA 算法深度解析