判断一个图是否存在负环时，通常使用 Bellman-Ford 算法及其变种实现。

Bellman-Ford 算法

见 （链接未公开）

在 Bellman-Ford 算法的运行过程中，若第 n 轮松弛仍然能更新某条边，则说明存在从源点可达的负环。

时间复杂度：O(nm)，额外空间复杂度：O(1)。

SPFA 算法

SPFA 算法，作为 Bellman-Ford 算法的变种，也可以用于负环判断。

相比于 Bellman-Ford 算法，SPFA 算法少了外层循环，通过队列进行优化，所以 SPFA 算法并不能直接通过循环次数判断负环。

通常，SPFA 算法依靠路径边数或者入队次数来判断负环。

路径边数

引入一个额外数组 l 记录最短路径边数，每次用节点 u 和边 e 松弛 v 成功时，令 l[v] := l[u] + 1。若某条最短路径的边数达到 n，说明负环存在。

constexpr int INF = 1e9;
size_t l[MAXN];

bool spfa(size_t s, size_t n) // false 表示有负环
{
    for (size_t i = 1; i <= n; i++)
    {
        vertices[i].dis = INF;
    }
    vertices[s].dis = 0;
    queue<size_t> qu;
    qu.push(s);
    l[s] = 0;
    while (!qu.empty())
    {
        size_t u = qu.front();
        qu.pop();
        for (Edge *e = vertices[u].first; e; e = e->next)
        {
            size_t v = e->to;
            if (vertices[u].dis + e->w < vertices[v].dis)
            {
                vertices[v].dis = vertices[u].dis + e->w;
                l[v] = l[u] + 1;
                if (l[v] >= n)
                {
                    return false;
                }
                qu.push(v);
            }
        }
    }
    return true;
}

时间复杂度：O(nm)，额外空间复杂度：O(n)。

入队次数

入队相当于 Bellman-Ford 算法的松弛操作，因为 Bellman-Ford 算法中，循环外层不能超过 n 次，因此可以通过记录每个点的入队次数是否达到 n 来判断有无负环。实现时通常用 is_in_queue 避免同一个点在队列中重复出现。

size_t cnts[MAXN];
bool is_in_queue[MAXN];

bool spfa(size_t s, size_t n) // false 表示有负环
{
    for (size_t i = 1; i <= n; i++)
    {
        vertices[i].dis = INF;
    }
    vertices[s].dis = 0;
    queue<size_t> qu;
    qu.push(s);
    is_in_queue[s] = true;
    cnts[s] = 1;
    while (!qu.empty())
    {
        size_t u = qu.front();
        qu.pop();
        is_in_queue[u] = false;
        for (Edge *e = vertices[u].first; e; e = e->next)
        {
            size_t v = e->to;
            if (vertices[u].dis + e->w < vertices[v].dis)
            {
                vertices[v].dis = vertices[u].dis + e->w;
                if (!is_in_queue[v])
                {
                    qu.push(v);
                    is_in_queue[v] = true;
                    cnts[v]++;
                    if (cnts[v] >= n)
                    {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}