判负环的真相：为何应关注路径边数而非入队次数

在学习 SPFA 判负环时，几乎所有入门教程都会告诉你一句话：“如果某个点入队超过 $n$ 次，则图中存在负环。”

停，这句话只对了一半。

如果你在考场上死守这个准则，你可能会面临两个结果：要么在某些特定构造的图中莫名其妙地 TLE，要么在逻辑推导中感到一丝违和。今天我们通过逻辑推演，把这个“坑”彻底填平。

1. 逻辑的错位：入队 $

eq$ 路径我们要判定的底层逻辑是鸽巢原理（Pigeonhole Principle）：

在一个含有 $n$ 个顶点的图中，任意两条简单路径之间，边数最多只有 $n-1$ 条。

如果存在一条路径包含了 $n$ 条边，说明这条路径一定经过了至少 $n+1$ 个顶点。根据鸽巢原理，其中必有两个顶点是重合的——这就是环。由于我们在跑最短路（不断松弛），这个环只能是负环。

入队次数： 是算法运行的“步数”，受入队先后顺序影响。
路径边数： 是图中节点间的“拓扑层级”，是客观存在的几何属性。

2. 为什么要数“边数”？

很多选手的代码习惯是这样的：

if (++cnt[v] >= n) return true; // 记录入队次数

这种写法在大多数随机图中没问题。但在网格图或链式结构中，SPFA 的入队次数可能会出现惊人的冗余。你可能在还没找到负环前，就已经因为大量的重复入队浪费了过多的时间。

更稳健、更快速的写法：记录当前最短路经过了多少条边。 我们需要维护一个 edge_cnt[v] 数组，表示从源点到 $v$ 的当前最短路径包含的边数。

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

3. 代码

看这段对比，干货就在注释里：

// 推荐的硬核写法
if (dist[v] > dist[u] + weight) {
    dist[v] = dist[u] + weight;
    edge_cnt[v] = edge_cnt[u] + 1; // 路径边数直接继承并加1

    // 关键点：判定条件是边数达到 n
    if (edge_cnt[v] >= n) {
        return true; // 铁证如山：发现负环
    }

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

4. 为什么它更快？

记录“路径边数”能让你第一时间捕捉到逻辑上的矛盾。一旦松弛操作导致某条路径长度达到 $n$，逻辑链条立即闭环，算法原地报错退出。而记录“入队次数”则带有一定的随机性，它取决于队列中节点的处理顺序，往往会多绕几个圈子才后知后觉。

金句提炼： “要把算法看作几何结构的演变。入队次数是过程，路径边数才是本质。”