SPFA

大佬教程收集整理的这篇文章主要介绍了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;
    }
}

大佬总结

以上是大佬教程为你收集整理的SPFA全部内容，希望文章能够帮你解决SPFA所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。