SPFA

Shortest Path Faster Algorithm — a queue-based refinement of Bellman-Ford that only relaxes edges out of vertices whose distance actually changed. Fast on typical graphs, $O(VE)$ in the worst case.

vector<long long> spfa(int n, int s, vector<vector<pair<int,int>>>& adj) {
    const long long INF = LLONG_MAX / 4;
    vector<long long> dist(n, INF);
    vector<int> inQueue(n, 0), cnt(n, 0);
    deque<int> q;
 
    dist[s] = 0; q.push_back(s); inQueue[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        inQueue[u] = 0;
        for (auto [v, w] : adj[u])
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    if (++cnt[v] > n) return {};      // negative cycle
                    q.push_back(v); inQueue[v] = 1;
                }
            }
    }
    return dist;
}

The inQueue flag is what makes it faster than plain Bellman-Ford: a vertex already waiting to be processed is not queued twice.

Negative cycle detection

Count how many times each vertex is enqueued. If any vertex enters the queue more than $n$ times, a negative cycle is reachable from the source. (Counting relaxations along a path — tracking the number of edges on the current best path and failing at $n$ — is a slightly stronger and equally cheap check.)

Why it can be hacked

SPFA is not safe on Codeforces

The worst case is $O(VE)$, and adversarial graphs that force it are well known and easy to generate. Problem setters routinely include anti-SPFA tests. It has been a running joke since the blog post titled “SPFA is dead” — do not submit plain SPFA on a problem where $O(VE)$ would TLE.

Mitigations that help but do not fix the worst case:

• SLF (Small Label First). Before pushing $v$, if dist[v] < dist[q.front()], push to the front instead of the back. This is a generalisation of 0-1 BFS’s deque trick.
• LLL (Large Label Last). Keep rotating the front to the back while dist[front] > average(dist in queue).
• Both together (SLF+LLL) are the common “optimised SPFA”, and both are still hackable.

When to actually use it

Situation	Use
Non-negative weights	Dijkstra — never SPFA
Negative weights, need a guarantee	Bellman-Ford
All-pairs with negatives, sparse	Johnson
Min-cost flow inner loop	Bellman-Ford once for potentials, then Dijkstra
Difference constraints	Bellman-Ford (or SPFA if the graph is random-ish and $VE$ is safe)

SPFA’s honest niche is difference-constraint systems and small graphs with negative weights, where its practical speed is convenient and its worst case is still within the limit.

Difference constraints

A system of constraints $x_j-x_i\le c$ becomes a graph with edge $i\to j$ of weight $c$. Shortest paths from a super-source connected to everything with weight 0 give a feasible assignment; a negative cycle means the system is infeasible. This is the main reason to keep a negative-weight shortest path algorithm in your toolkit at all.

See also: Bellman-Ford · Negative Cycles · Shortest Paths