The Truth About Negative Cycle Detection: Why Focus on Edge Count Instead of Queue Count

When learning about SPFA for negative cycle detection, almost all introductory tutorials will tell you one thing: “If a node is enqueued more than $n$ times, then there exists a negative cycle in the graph.”

Stop, this statement is only half correct.

If you stubbornly adhere to this principle during an examination, you might face two outcomes: either you experience inexplicable TLE on certain specially constructed graphs, or you feel a sense of dissonance in your logical deductions. Today, we will thoroughly fill this “pit” through logical reasoning.

1. Logical Misalignment: Enqueue Count $

eq$ Path The underlying logic we need to determine is the Pigeonhole Principle:

In a graph with $n$ vertices, the maximum number of edges between any two simple paths is $n-1$.

If there exists a path that contains $n$ edges, it indicates that this path must have traversed at least $n+1$ vertices. According to the pigeonhole principle, at least two of these vertices must coincide—this forms a cycle. Since we are running the shortest path algorithm (constantly relaxing), this cycle can only be a negative cycle.

• Enqueue Count: Represents the “steps” of the algorithm, influenced by the order of enqueueing.
• Path Edge Count: Represents the “topological hierarchy” between nodes in the graph, an objectively existing geometric property.

2. Why Count “Edges”?

Many competitors have coding habits like this:

if (++cnt[v] >= n) return true; // Record enqueue count

This approach is fine in most random graphs. However, in grid graphs or chain structures, the enqueue count of SPFA may exhibit astonishing redundancy. You may waste excessive time due to numerous repeated enqueues before even finding a negative cycle.

A more robust and faster approach: record how many edges the current shortest path has traversed. We need to maintain an edge_cnt[v] array that represents the number of edges in the current shortest path from the source to $v$.

$$edge ext{ }cnt[v] = edge ext{ }cnt[u] + 1$$

3. Code

Here’s a comparative look; the essence lies in the comments:

// Recommended hardcore implementation
if (dist[v] > dist[u] + weight) {
    dist[v] = dist[u] + weight;
    edge_cnt[v] = edge_cnt[u] + 1; // Path edge count directly inherits and adds 1

    // Key point: The condition for detection is that the edge count reaches n
    if (edge_cnt[v] >= n) {
        return true; // Solid evidence: negative cycle detected
    }

    if (!vis[v]) {
        q.push(v);
        vis[v] = true;
    }
}

4. Why Is It Faster?

Recording the “path edge count” allows you to capture logical contradictions immediately. Once a relaxation operation causes the length of a path to reach $n$, the logical chain closes immediately, and the algorithm exits with an error. In contrast, recording the “enqueue count” carries a degree of randomness, depending on the order in which nodes in the queue are processed, often taking several loops before realizing the issue.

Quotable Insight: “View algorithms as the evolution of geometric structures. The enqueue count is the process, while the path edge count is the essence.”