Negative cycle detection has long been associated with a "black magic": DFS-based SPFA. It is said to be hundreds of times faster at detecting negative cycles than the BFS version. Consequently, many competitors regard it as a sacred technique, until one day they encounter a carefully constructed "trap graph" on the competition field, watching helplessly as the complexity of $O(VE)$ degenerates into exponential.
Why Is It Fast?
The core logic of DFS-based SPFA is: search down the current path; if a node already in the stack is found, a negative cycle is immediately detected.
// Core logic snippet
bool dfs_spfa(int u) {
instack[u] = true;
for (auto edge : adj[u]) {
if (dist[edge.v] > dist[u] + edge.w) {
dist[edge.v] = dist[u] + edge.w;
if (instack[edge.v] || dfs_spfa(edge.v)) return true;
}
}
instack[u] = false;
return false;
}- BFS searches layer by layer, possibly requiring several rounds to accumulate $edge ext{_cnt}$ to $n$; whereas DFS is like a sharp knife, able to instantly backtrack as soon as there is a cycle on the path.
- In graphs where a negative cycle truly exists, the DFS version is almost instantaneous.
Why Is It Dangerous?
Success and failure both hinge on backtracking. The essence of DFS is to prioritize deep exploration. If there is no negative cycle in the graph but there are significantly varying multi-layer negative weight paths, DFS can fall into an extremely perilous state:
Each time it discovers a shorter "shortcut" through a negative weight edge, it mercilessly overturns all previously traversed successor nodes, forcing them to re-enter the recursion stack.
"Normal variations only lead to constant overhead, but a ‘multiplicative decreasing level structure’ turns DFS into a physical binary counter. The logic of a binary counter corresponds directly to an algorithmic time complexity of $O(2^n)$ exponential explosion.
Diamond Chain (Layered Diamond Graph)
To construct an $n$-layer structure, each layer contains two nodes.
- Inter-layer relationship: There are two paths from each layer $i$ to the next layer $i+1$.
- Path A (induced path): High edge weight, e.g., $W_i = 2^{n-i}$.
- Path B (short path): Slightly lower edge weight, e.g., $w_i = 0$.
Quotable Insight:
"In algorithm competitions, stability is more important than explosiveness. DFS-SPFA is like a toxic forbidden drug; it can make you run incredibly fast, but it can also lead to your 'explosion' just before the finish line."