Overcoming Blind Spots in Negative Cycle Detection: Strategies with Super Source

When solving negative cycle problems on platforms like Luogu or Codeforces, have you ever encountered this bizarre situation: Your code logic is identical to the solution, SPFA runs quickly and converges smoothly, but upon submission—all wrong (WA).

The reason may be simple: your negative cycle is hiding in a place you cannot “see.”

1. Fatal Blind Spot: Limitations of Starting from Node 1

Most contestants habitually write:

    dist[1] = 0; q.push(1); vis[1] = true;

Logical Flaw: If the graph is disconnected (or if you cannot reach a certain connected component from node 1), and the negative cycle happens to be in that unreachable area, SPFA will never trigger a relaxation operation, let alone detect the negative cycle.

Conclusion: The detection of negative cycles is not about “checking if there is a negative cycle in the shortest path starting from 1,” but rather “determining if there is a negative cycle in the entire graph.”

2. Solution A: Establishing a “Super Source”

This is an extremely classic modeling technique.

Procedure:

1. Create a fictitious node $S$ (usually numbered $0$ or $n+1$).
2. Connect $S$ to all nodes in the graph $1 o n$ with directed edges of weight $0$.
3. Run SPFA starting from $S$.

Mathematical Essence: This ensures that starting from $S$, you can reach any corner of the graph. If there exists any negative cycle in the graph, it will certainly be captured.

3. Solution B: All-in Queue Method (Recommended Approach)

To avoid the hassle of creating a fictitious node, we usually adopt a more efficient initialization method:

// Core pseudocode: Correct initialization for negative cycle detection
for (int i = 1; i <= n; ++i) {
    dist[i] = 0;    // Initialize all distances to 0
    vis[i] = true;  // Mark all as in the queue
    q.push(i);      // Push all nodes into the queue at once
}

while (!q.empty()) {
    int u = q.front(); q.pop(); vis[u] = false;
    // ... Subsequent normal relaxation and cnt[v] >= n check
}

Why is this correct? This is equivalent to simultaneously initiating searches from $n$ starting points. As long as there is a negative cycle anywhere in the graph, the relaxation operations will trigger like a chain reaction of dominoes, ultimately pointing to that contradictory cycle.

In the difference constraint system, this pitfall also exists. If your problem requires checking whether a system of inequalities has a solution, and you only start from one point, the potential oversights may not only include a negative cycle but also the validity of the entire system.

Key Insight: “Do not focus solely on the starting point; maintain a global perspective.”