SPFA, in depth: queue-based Bellman-Ford, its real worst case, negative-cycle detection and when to choose it

From Bellman-Ford to a queue

Relaxing edge u to v with weight w means: if dist[u] + w is less than dist[v], set dist[v] to that value and record u as v's parent. Bellman-Ford relaxes every edge, V minus 1 times. After round k, every vertex whose shortest path uses at most k edges has its final distance, and since a shortest path in a graph without negative cycles is simple, V minus 1 rounds suffice.

Now look at a single relaxation. It can only succeed if dist[u] changed since the last time edge u to v was examined. If u's distance is the same as last round, re-relaxing its outgoing edges does nothing. So keep a set of vertices whose distance has improved and not yet been propagated, and only scan their outgoing edges. Use a FIFO queue for that set, add a flag so a vertex is never in the queue twice, and you have SPFA. The algorithm is essentially Moore's 1959 queue-based variant of Bellman-Ford; the SPFA name comes from a 1994 paper by Duan Fanding and is mostly used in competitive programming circles.

The invariant that makes it correct: at every moment, any edge u to v that could still be relaxed has u in the queue. It holds initially, because only the source has a finite distance and it is queued. It is preserved, because when u is popped all its edges are relaxed, and any vertex whose distance drops is pushed. When the queue empties, no edge can be relaxed, which is exactly the condition that dist holds shortest-path distances.

An implementation you can trust

The version below is the one to copy. It counts the number of edges on the current best path to each vertex, rather than how many times the vertex was enqueued, and reports a negative cycle as soon as any path reaches n edges. A simple path has at most n minus 1 edges, so a path with n edges must repeat a vertex, and since it is a shortest-so-far path, the repeated loop has negative weight.

from collections import deque

def spfa(n, adj, src):
    """adj[u] = list of (v, w). Returns (dist, parent) or raises with a vertex on/after a negative cycle."""
    INF = float("inf")
    dist = [INF] * n
    hops = [0] * n          # edges on the current best path to each vertex
    parent = [-1] * n
    in_queue = [False] * n
    dist[src] = 0
    q = deque([src])
    in_queue[src] = True
    while q:
        u = q.popleft()
        in_queue[u] = False
        du = dist[u]
        for v, w in adj[u]:
            if du + w < dist[v]:
                dist[v] = du + w
                parent[v] = u
                hops[v] = hops[u] + 1
                if hops[v] >= n:
                    raise NegativeCycle(v, parent)
                if not in_queue[v]:
                    q.append(v)
                    in_queue[v] = True
    return dist, parent

class NegativeCycle(Exception):
    def __init__(self, v, parent):
        super().__init__(f"negative cycle reachable from source (through vertex {v})")
        self.v, self.parent = v, parent

The common alternative counts enqueues and declares a cycle when a vertex has been enqueued n times. It is also correct, but it can wait much longer, because a vertex may be enqueued many times before the count reaches n. The hop count fires as soon as some current best path reaches n edges, which in practice usually happens earlier. Read dist[u] once per pop, as above, and use exact integer weights where you can.

Worked example, traced

Take five vertices S, A, B, C, D and seven edges: S to A weight 6, S to B 2, B to A 3, A to C minus 4, B to C 5, C to D 2, A to D 1. Adjacency lists are in that order. The table shows each pop, the queue after the pop's relaxations, and the distances. These rows were produced by running the code above.

SPFA made 8 pops and examined 10 edges. Bellman-Ford with this edge order would examine 7 edges per round for V minus 1, that is 4, rounds: 28 examinations, fewer only with an early exit. The saving comes from scanning only vertices whose distance had just changed: S and B once each, A, C and D twice. The parent array ends as A from B, B from S, C from A, D from C, which is the shortest-path tree.

Now add one edge, C to B with weight minus 3. The loop B to A to C to B weighs 3 minus 4 minus 3, which is minus 4, so going round it again always gets cheaper. Running the same code, the hop count of C reaches 5 on the ninth pop and the function raises. To recover the cycle, walk parent pointers from the reported vertex with a visited set until a vertex repeats; the loop from that vertex back to itself is the cycle. Here that yields B, A, C. Be careful: in SPFA a parent pointer can be stale, because an ancestor may have improved again without being popped, so the walk can reach the source instead. Never index with the source's -1 parent; stop there and fall back to a Bellman-Ford pass with the extraction described in the negative-cycle article linked above.

Complexity: the honest version

With a FIFO queue, SPFA's work can be grouped into passes the same way Bellman-Ford's can. Every vertex whose best path has k edges is finalised by the end of pass k, and each pass scans each edge at most once. So the worst case is O(VE), exactly Bellman-Ford's. It is not better in the worst case, it is only better when few vertices change per pass.

Many sources state that SPFA runs in O(kE) on average with a small constant k, often quoted as about 2. There is no proof of that, and it is false on adversarial graphs. Grid-shaped graphs with carefully chosen weights, and graphs where many long paths are slightly cheaper than short ones, force vertices to be re-improved many times and drive SPFA close to its V times E bound. Competitive programmers learned this when problem setters began adding such tests specifically to defeat it.

The popular heuristics do not repair this. Small Label First pushes a vertex to the front of a deque when its distance is below the front's, and Large Label Last rotates large labels to the back. Both help on some inputs, but both break the pass structure that gives the O(VE) bound, and inputs exist on which they are slower than plain FIFO. Treat SPFA as Bellman-Ford with a good best case, never as a faster algorithm.

Choosing between SPFA and its neighbours

If weights are non-negative, do not use SPFA at all; Dijkstra's Algorithm, in depth is both faster and guaranteed. For 0 and 1 weights see 0-1 BFS, in depth, and for DAGs a single relaxation pass in topological order is linear even with negative weights.

Where SPFA earns its keep

Difference constraints are the classic application. A system of constraints x_j minus x_i is at most c becomes a graph with an edge from i to j of weight c. Add a virtual source with zero-weight edges to every variable; if the graph has a negative cycle the system is infeasible, otherwise the shortest distances are a feasible assignment. Scheduling problems such as 'task B starts at least 3 units after A ends, and no more than 10 after' map directly onto this.

def solve_difference_constraints(n, constraints):
    """constraints: list of (i, j, c) meaning x[j] - x[i] <= c. Returns x or None if infeasible."""
    src = n
    adj = [[] for _ in range(n + 1)]
    for i, j, c in constraints:
        adj[i].append((j, c))
    for v in range(n):
        adj[src].append((v, 0))
    try:
        dist, _ = spfa(n + 1, adj, src)
    except NegativeCycle:
        return None
    return dist[:n]

The second strength is warm starting. If you have correct distances and an edge u to v gets cheaper, relax it, and if dist[v] improves, start SPFA with only v in the queue and the existing arrays. Only vertices whose distance actually changes are touched, which is often a tiny fraction of the graph. Edge increases are harder, because they can invalidate a subtree; the simple safe approach is to reset the subtree under the changed edge in the parent tree and recompute from its boundary.

Min-cost flow uses the same structure: successive shortest path implementations often run SPFA on the residual graph, which has negative-cost reverse edges. A more robust pattern is to run Bellman-Ford or SPFA once to compute potentials, then use Dijkstra with reduced costs for every augmentation.

Pitfalls in real code

• Infinity arithmetic. With integers, INF plus a negative weight can still look finite, or overflow when INF is close to the type's maximum. Skip popped vertices whose distance is INF; in this implementation only reached vertices are ever queued, which avoids it.
• Unreachable cycles. SPFA from a source only detects negative cycles reachable from that source. To test a whole graph, use a virtual source with zero edges to every vertex, as in the difference-constraints code.
• Floating-point weights. Currency arbitrage uses minus log of rates, and rounding noise can create tiny fake negative cycles. Relax only when the improvement exceeds a small epsilon, and verify any reported cycle by summing its weights exactly.
• No duplicate guard. Without the in-queue flag, the queue can grow far beyond n and the algorithm does redundant work. With it, the queue never holds more than n vertices.
• Using it as a Dijkstra replacement. On non-negative graphs SPFA wins on some inputs and degrades badly on others; the variance is the problem, not the average.
• Unbounded latency. In a service, put a cap on relaxations proportional to V times E and alert on runs that approach it; that is your signal that the input shape changed.

What to do next

1. Check whether your weights can be negative at all; if not, use Dijkstra and stop here.
2. If the graph is a DAG, relax in topological order instead; it is linear and exact.
3. Implement SPFA with the in-queue flag and hop-count cycle detection exactly as above, and keep integer weights where possible.
4. Test it against plain Bellman-Ford on random graphs, including ones with planted negative cycles, and compare distances and cycle reports.
5. Add a grid-shaped adversarial test and measure relaxations, so you know your worst case before production does.
6. For dynamic inputs, add the warm-start path for edge decreases, and recompute on increases.
7. Instrument relaxation counts and alert when they approach V times E.