判负环，一直流传着一个“黑魔法”：DFS 版 SPFA。据说它判断负环的速度比 BFS 版快上百倍。于是，很多选手将其奉为圭臬，直到某天他们在赛场上遇到了精心构造的“卡图”，眼睁睁看着 $O(VE)$ 的复杂度退化成了指数级。
为什么它快？
DFS 版 SPFA 的核心逻辑是：沿着当前的路径一路向下搜，如果搜到了正在栈中的节点，则立即判定存在负环。
// 核心逻辑片段
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 是一层一层搜，可能要绕好几圈才能把 $edge ext{_cnt}$ 累加到 $n$；而 DFS 像一把尖刀，只要路径上有环，它能瞬间回溯。
- 在确实存在负环的图中，DFS 版几乎是秒杀。
为什么它危险？
成也回溯，败也回溯。DFS 的本质是优先走深。如果图中没有负环，但存在权值级差显著的多层负权路径，DFS 就会陷入一种极其恐怖的状态：
每当它通过一条负权边发现了一条更短的“捷径”，它就会无情地推翻之前已经遍历过的所有后继节点，并强迫它们重新进入递归栈。
“普通级差只会带来常数级的冗余，但‘成倍数递减的级差结构’会将 DFS 变成一个物理意义上的二进制计数器。二进制计数器的逻辑，在算法时间复杂度上直接对应 $O(2^n)$ 指数级爆炸。
层级菱形图 (Diamond Chain)
要构造 $n$ 层结构，每层包含两个节点。
- 层间关系：每一层 $i$ 到下一层 $i+1$ 都有两条路径。
- 路径 A（诱导路）：边权很大，例如 $W_i = 2^{n-i}$。
- 路径 B（短路径）：边权略小，例如 $w_i = 0$。
金句提炼：
“在算法竞赛中，稳定比爆发更重要。DFS-SPFA 就像是带毒的禁药，它能让你跑得飞快，也能让你在终点线前‘爆体而亡’。”