带负权的单源最短路（Bellman-Ford&&SPFA）

超、凢脫俗 2024-04-17 22:00 62阅读 0赞

# 带负权的单源最短路（Bellman-Ford&&SPFA） #

这次终于遇到带负权的单源最短路了，以前遇到的都是权值为正的情况，直接跑个**Dijkstra算法**即可

这次也终于能好好学学**Bellman-Ford算法和SPFA算法**了（Bellman-Ford算法的优化（用队列））

下面的博客，感觉很好，代码简单，而且用**结构体和vector**都有模板

[https://blog.csdn.net/AAMahone/article/details/90085637][https_blog.csdn.net_AAMahone_article_details_90085637]

给道例题：  
[https://nanti.jisuanke.com/t/41305][https_nanti.jisuanke.com_t_41305]

就是今天的网络赛题签到题，弱鸡只会做签到题（呜呜呜）（**The Preliminary Contest for ICPC Asia Nanjing 2019**）

开始队友准备开其他题，后面我看榜发现这题似乎是个签到题，于是就开始看题，由于太菜，看了很久才知道原来就是一个最短路的问题，比赛结束之后自己又好好做了这题，用了四种方式都尝试了下：

**Bellman-Ford算法实现：（vector表示）**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<vector>
    using namespace std;
    const int maxn=550;
    const int inf=0xffffff0;
    typedef pair<int,int> pii;
    int dis[maxn];
    vector<pii> e[maxn];
    void init(int  n)
    {
        
        for(int i=0;i<n;i++)
            e[i].clear();
    }
    bool Bellman_Ford(int n,int st)
    {
        
        for(int i=0;i<=n;i++)
        {
        
            dis[i]=inf;
        }
        dis[st]=0;
        int len;
        for(int k=0;k<n-1;k++)
        {
        
            for(int i=0;i<=n;i++)
            {
        
                len=e[i].size();
                for(int j=0;j<len;j++)
                {
        
                    if(dis[e[i][j].first]>dis[i]+e[i][j].second)
                    {
        
                        dis[e[i][j].first]=dis[i]+e[i][j].second;
                    }
                }
            }
        }
        for(int i=0;i<=n;i++)
        {
        
            len=e[i].size();
            for(int j=0;j<len;j++)
            {
        
                if(dis[e[i][j].first]>dis[i]+e[i][j].second)
                    return false;
            }
        }
        return true;
    }
    int main()
    {
        
        int t;
        int n,m;
        int u,v,w;
        int a,b;
        scanf("%d",&t);
        while(t--)
        {
        
            scanf("%d%d",&n,&m);
            init(n);
            for(int i=0;i<m;i++)
            {
        
                scanf("%d%d%d",&u,&v,&w);
                e[u].push_back(make_pair(v,w));
            }
            for(int i=0;i<6;i++)
            {
        
                scanf("%d%d",&a,&b);
                if(Bellman_Ford(n,b))
                {
        
                    dis[a]=0-dis[a];
                    printf("%d\n",dis[a]);
                    e[a].push_back(make_pair(b,dis[a]));
                }
            }
        }
        return 0;
    }

![在这里插入图片描述][20190901224252640.png]

**Bellman-Ford算法实现：（结构体数组）**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    const int maxn=550;
    const int inf=0xffffff0;
    struct node
    {
        
        int v,w,nxt;
    }e[maxn];
    int dis[maxn];
    int head[maxn];
    int tot=0;
    void init()
    {
        
        tot=0;
        memset(head,-1,sizeof(head));
    }
    void add(int u,int v,int w)
    {
        
        e[tot].v=v;
        e[tot].w=w;
        e[tot].nxt=head[u];
        head[u]=tot++;
    }
    bool Bellman_Ford(int n,int st)
    {
        
        for(int i=0;i<=n;i++)
            dis[i]=inf;
        dis[st]=0;
        for(int k=0;k<n-1;k++)
        {
        
            for(int i=0;i<=n;i++)
            {
        
                for(int j=head[i];j!=-1;j=e[j].nxt)
                {
        
                    if(dis[e[j].v]>dis[i]+e[j].w)
                        dis[e[j].v]=dis[i]+e[j].w;
                }
            }
        }
        for(int i=0;i<=n;i++)
        {
        
            for(int j=head[i];j!=-1;j=e[j].nxt)
            {
        
                if(dis[e[j].v]>dis[i]+e[j].w)
                {
        
                    return false;
                }
            }
        }
        return true;
    }
    int main()
    {
        
        int t;
        int n,m;
        int a,b;
        int u,v,w;
        scanf("%d",&t);
        while(t--)
        {
        
            scanf("%d%d",&n,&m);
            init();
            for(int i=0;i<m;i++)
            {
        
                scanf("%d%d%d",&u,&v,&w);
                add(u,v,w);
            }
            for(int i=0;i<6;i++)
            {
        
                scanf("%d%d",&a,&b);
                if(Bellman_Ford(n,b))
                {
        
                    dis[a]=0-dis[a];
                    printf("%d\n",dis[a]);
                    add(a,b,dis[a]);
                }
            }
        }
        return 0;
    }

![在这里插入图片描述][20190901224505371.png]

**SPFA算法实现：（vector）**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<vector>
    #include<queue>
    #include<algorithm>
    using namespace std;
    const int maxn=550;
    const int inf=0xffffff0;
    typedef pair<int,int>pii;
    vector<pii>e[maxn];
    int dis[maxn];
    int head[maxn];
    int cnt[maxn];
    int vis[maxn];
    void init(int n)
    {
        
        for(int i=0;i<=n;i++)
            e[i].clear();
    }
    bool SPFA(int n,int st)
    {
        
        for(int i=0;i<=n;i++)
        {
        
            dis[i]=inf;
            vis[i]=0;
            cnt[i]=0;
        }
        dis[st]=0;
        int cur,len;
        queue<int>q;
        q.push(st);
        vis[st]=1;
        cnt[st]++;
        while(!q.empty())
        {
        
            cur=q.front();
            q.pop();
            vis[cur]=0;
            len=e[cur].size();
            for(int i=0;i<len;i++)
            {
        
                if(dis[e[cur][i].first]>dis[cur]+e[cur][i].second)
                {
        
                    if(!vis[e[cur][i].first])
                    {
        
                        cnt[e[cur][i].first]++;
                        q.push(e[cur][i].first);
                        vis[e[cur][i].first]=1;
                        if(cnt[e[cur][i].first]>=n)
                            return false;
                    }
                    dis[e[cur][i].first]=dis[cur]+e[cur][i].second;
                }
            }
        }
        return true ;
    }
    int  main()
    {
        
        int t;
        int n,m;
        int a,b;
        int u,v,w;
        scanf("%d",&t);
        while(t--)
        {
        
            scanf("%d%d",&n,&m);
            init(n);
            for(int i=0;i<m;i++)
            {
        
                scanf("%d%d%d",&u,&v,&w);
                e[u].push_back(make_pair(v,w));
            }
            for(int i=0;i<6;i++)
            {
        
                scanf("%d%d",&a,&b);
                if(SPFA(n,b))
                {
        
                    dis[a]=0-dis[a];
                    printf("%d\n",dis[a]);
                    e[a].push_back(make_pair(b,dis[a]));
                }
            }
        }
        return 0;
    }

![在这里插入图片描述][20190901224521270.png]  
SPFA算法：（结构体数组）

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<queue>
    #include<algorithm>
    using namespace std;
    const int maxn=550;
    const int inf=0xffffff0;
    struct node
    {
        
        int v,w,nxt;
    }e[maxn];
    int dis[maxn],vis[maxn],cnt[maxn],head[maxn],tot=0;
    void init()
    {
        
        tot=0;
        memset(head,-1,sizeof(head));
    }void add(int u,int v,int w)
    {
        
        e[tot].v=v;
        e[tot].w=w;
        e[tot].nxt=head[u];
        head[u]=tot++;
    }
    bool SPFA(int n,int st)
    {
        
        for(int i=0;i<=n;i++)
        {
        
            dis[i]=inf;
            vis[i]=0;
            cnt[i]=0;
        }
        dis[st]=0;
        int cur;
        queue<int>q;
        q.push(st);
        vis[st]=1;
        cnt[st]++;
        while(!q.empty())
        {
        
            cur=q.front();
            q.pop();
            vis[cur]=0;
            for(int i=head[cur];i!=-1;i=e[i].nxt)
            {
        
                if(dis[e[i].v]>dis[cur]+e[i].w)
                {
        
                    if(!vis[e[i].v])
                    {
        
                        cnt[e[i].v]++;
                        q.push(e[i].v);
                        vis[e[i].v]=1;
                        if(cnt[e[i].v]>=n)
                        {
        
                            return false;
                        }
                    }
                    dis[e[i].v]=dis[cur]+e[i].w;
                }
            }
        }
        return true;
    }
    int main()
    {
        
        int t;
        int n,m;
        int a,b;
        int u,v,w;
        scanf("%d",&t);
        while(t--)
        {
        
            scanf("%d%d",&n,&m);
            init();
            for(int i=0;i<m;i++)
            {
        
                scanf("%d%d%d",&u,&v,&w);
                add(u,v,w);
            }
            for(int i=0;i<6;i++)
            {
        
                scanf("%d%d",&a,&b);
                if(SPFA(n,b))
                {
        
                    dis[a]=0-dis[a];
                    printf("%d\n",dis[a]);
                    add(a,b,dis[a]);
                }
            }
        }
        return 0;
    }

![在这里插入图片描述][20190901224536869.png]

[https_blog.csdn.net_AAMahone_article_details_90085637]: https://blog.csdn.net/AAMahone/article/details/90085637
[https_nanti.jisuanke.com_t_41305]: https://nanti.jisuanke.com/t/41305
[20190901224252640.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/2ada5d309d694943aed4d5289421344b.png
[20190901224505371.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/3660f010382d404d9092a68696b56add.png
[20190901224521270.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/f3a8c238e07849eeb107a637bd815e26.png
[20190901224536869.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b0afd0e2231f47169ba6f70d4a003070.png