使用spfa可以判断图中是否存在负环

思路

在原spfa算法的基础上，加一个cnt[N]数组， 这个数组cnt[i]用于存当前到达i的时候路径最短，所需要的边数。

if(dist[j] > dist[temp] + w[temp][j])
{
    dist[j] = dist[temp] + w[temp][j];
    cnt[j] = cnt[temp] + 1; //到达j的最短路径就是到达temp的最短路径 + 1.
}

当cnt[temp1] == n的时候 ， 当有某个结点temp1的最短路径经过了n条边的时候

由于总共有n个结点， 当经过n条边的时候，则代表必定至少存在一个负权回路。

代码

void spfa()
{
    queue<int> q;  //同时此题由于不求最短路径的值，所以dist完全无需初始化，当a -> b时 如果 w[a][b] > 0 则自然dist[a] < dist[a] + w[a][b]  如果 a - > b ,而w[a][b] < 0的时候，则自然dist[a] > dist[a] + w[a][b]，所以无需算出精确的dist[]值，只需要通过dist[]值判断是否需要更新将结点加入到队列中即可。
    for(int i = 1 ; i <= n ; i++)
    {
        q.push(i);
        choose[i] = 1;
    }
    while(q.size())
    {
        int temp = q.front();
        q.pop();
        choose[temp] = 0;
        for(int i = h[temp] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[temp] + w[i])
            {
                dist[j] = dist[temp] + w[i];
                cnt[j] = cnt[temp] + 1;
                if(cnt[j] == n)  //当存在了某个结点有n条边的时候，则无需再算了，直接返回即可，代表存在有负权回路
                {
                    printf("Yes\n");
                    return;
                }
                if(!choose[j])
                {
                    q.push(j);
                }
            }
        }
    }
    printf("No\n");
    return;
}