SPFA

SPFA

SPFA能处理负边权，可以判断负环。也可以求最长路。

最短路

#include <queue>
queue<int> q;
void SPFA(int s)
{
    fill(dis + 1, dis + 1 + n, 2147483647); //初始边无限大
    memset(vis, 0, sizeof vis);
    dis[s] = 0;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = head[x]; i != -1; i = t[i].nxt)
        {
            int y = t[i].to, z = t[i].w;
            if (dis[y] > dis[x] + z)
            {
                dis[y] = dis[x] + z;
                if (vis[y] == 0)
                {
                    q.push(y);
                    vis[y] = 1;
                }
            }
        }
    }
}

最长路

可依据最短路代码进行修改。

1. dis 数组赋初值时，如果没有负边权就赋 \(-1\) ，如果有负边权就赋无限小。

2. 把 dis[y]>dis[x]+z 中的 > 改成 < 。

判断负环

可在最短路代码基础上进行修改。需新加入一个数组 cnt ，专门记录负环。

补充代码：

ll cnt[maxn]; //专门记录负环
void SPFA().....if (dis[y] > dis[x] + z)
{
    dis[y] = dis[x] + z;
    cnt[y]++;
    if (cnt[y] >= n + 1) //出现超过n次表示就有负环
    {
        ans = 1; //ans=1代表有负环。
        return;
    }
    if (vis[y] == 0)
    {
        q.push(y);
        vis[y] = 1;
    }
}