SPFA

Shortest Path Faster Algorithm

• adj[v] = {next, dist}
• 음수 간선이 있어도 사용 가능
  • 사이클을 잡기 위해서 각 정점의 방문 수를 체크해서 MAX_V보다 커지면 탈출한다.
• 평균적으로 수행 시간이 빠른 알고리즘

int d[MAX_V], inQ[MAX_V];
fill(d, d + MAX_V, INF);
fill(inQ, inQ + MAX_V, 0);
d[S] = 0;
inQ[S] = 1;

queue<int> q;
q.push(S);

while(q.size()) {
    auto cur = q.top(); q.pop();
    inQ[cur] = 0;

    // Check Negative Loop here if you want
    // if (++cnt[cur] >= MAX_V || d[cur] < -INF) ~
    
    for(auto& t: adj[cur]) {
        int newDist = d[cur] + t.second;
        if (newDist < d[t.first]) {
            d[t.first] = newDist;
            if (inQ[t.first] == 0) {
                q.push(t.first);
                inQ[t.first] = 1;
            }
        }
    }
}

Shortest Path Construction

int d[MAX_V], inQ[MAX_V], pre[MAX_V];
fill(d, d + MAX_V, INF);
fill(inQ, inQ + MAX_V, 0);
fill(pre, pre + MAX_V, -1);
d[S] = 0;
inQ[S] = 1;

queue<int> q;
q.push(S);

while(q.size()) {
    auto cur = q.top(); q.pop();
    inQ[cur] = 0;

    // Check Negative Loop here if you want
    // if (++cnt[cur] >= MAX_V || d[cur] < -INF) ~
    for(auto& t: adj[cur]) {
        int newDist = d[cur] + t.second;
        if (newDist < d[t.first]) {
            d[t.first] = newDist;
            pre[t.first] = cur;
            if (inQ[t.first] == 0) {
                q.push(t.first);
                inQ[t.first] = 1;
            }
        }
    }
}

vector<int> getPath(int t) {
    vector<int> res;
    for(int p = t; p != S; p = pre[p]) {
        res.push_back(p);
    }
    res.push_back(S);
    reverse(res.begin(), res.end());

    return res;
}

Time Complexity

• Worst: $O(VE)$
• Best: $O(V + E)$