Y总方法 + 《算法导论》伪代码实现

Y总版，SPFA判断路径长度

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;
int e[M], ne[M], w[M], h[N], idx;
int n, m, dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool has_negative_ring()
{
    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    int a, b, c;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++)
        scanf("%d%d%d", &a, &b, &c), add(a, b, c);

    if(has_negative_ring()) puts("Yes");
    else puts("No");

    return 0;
}

N - 1轮松弛后，判断是否存在边(u, v)满足 v.d > v.u + w(u, v)

《算法导论》第3版

C++ 代码，不构建图（最快）

#include <cstring>
#include <iostream>

using namespace std;

const int N = 2010, M = 10010;

struct edge
{
    int a, b, c;
};

edge edges[M];
int n, m;
int dist[N];

bool has_negative_ring()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n - 1; i++)
    {
        for(int i = 0; i < m; i ++)
        {
            edge eg = edges[i];
            if(dist[eg.b] > dist[eg.a] + eg.c)
                dist[eg.b] = dist[eg.a] + eg.c;
        }
    }
    for(int i = 0; i < m; i ++)
    {
        edge eg = edges[i];
        if(dist[eg.b] > dist[eg.a] + eg.c)
            return true;
    }
    return false;
}

C++ 代码，邻接链表表示图

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2010, M = 10010, INF = 0x3f3f3f3f;
int e[M], ne[M], w[M], h[N], idx;
int n, m, dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool has_negative_ring()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n - 1; i ++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int t = h[j]; t != -1; t = ne[t])
            {
                int k = e[t], wjk = w[t];
                if(dist[k] > dist[j] + wjk)
                    dist[k] = dist[j] + wjk;
            }
        }
    }
    for(int j = 1; j <= n; j++)
    {
        for(int t = h[j]; t != -1; t = ne[t])
        {
            int k = e[t], wjk = w[t];
            if(dist[k] > dist[j] + wjk)
                return true;
        }
    }
    return false;
}