Algorithm - SPFA - INCLAVIC

Course

可以參考我做的課程簡報：

MST & Shortest Path

Shortest Path Faster Algorithm (SPFA)

單源最短路徑
利用 queue 加速的 Bellman-Ford，僅對需要的邊做鬆弛
枚舉起點鬆弛過的邊，而鬆弛過的點除非被重新鬆弛，否則不會更動

SPFA 可處理負邊、可以判斷是否有負環

生成步驟

從起點開始推入佇列，根據佇列中的點 a 與其相連的點 b 是否可鬆弛
- ( b 原本與根的距離 dist[b] 比從根經過 a 再到 b dist[a] + w[a][b] 還大)
更新根到 b 的距離 dist[b] 為 dist[a] + w[a][b]
將點 b 推入佇列

SPFA Example

Template

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2000+5;
const int INF = 0x3f3f3f3f;

struct Edge{
    int v;
    int w;
};

int N, M;
vector<Edge> G[maxn];

bool SPFA(int S){
    int cnt[maxn]; // 記錄此點被更新過幾次
    int dist[maxn];

    bool inqueue[maxn];
    queue<int> q;

    memset(cnt, 0, sizeof(cnt));
    memset(dist, INF, sizeof(dist));
    memset(inqueue, false, sizeof(inqueue));

    // 推入起點
    q.push(S);
    dist[S] = 0;
    inqueue[S] = true;
    cnt[S] = 1;

    while(!q.empty()){
        int now = q.front();
        q.pop();
        inqueue[now] = false;

        for(auto &e : G[now]){
            if(dist[e.v] > dist[now] + e.w){
                dist[e.v] = dist[now] + e.w;

                if(!inqueue[e.v]){
                    // 如果這個點被鬆弛過 N 次以上 代表存在負環
                    // 因為一個點最多跟 N-1 個點相連 最多更新 N-1 次
                    if(++cnt[e.v] >= N) return false;
                    
                    q.push(e.v);
                    inqueue[e.v] = true;
                }
            }
        }
    }
    return true;
}


int main(){
    int t;
    cin >> t;

    while(t--){
        cin >> N >> M;
        for(int i = 0; i <= N; ++i) G[i].clear();
        
        int u, v, w;
        for(int i = 0; i < M; ++i){
            cin >> u >> v >> w;
            // 有向圖
            G[u].push_back({v, w});
        }

        if(!SPFA(0)) cout << "possible" << endl;
        else cout << "not possible" << endl;
    }
}

UVA Problem

UVA00558 - Wormholes