Bellman_Ford算法->SPFA算法

Bellman_Ford算法->SPFA算法

刘汝佳算法入门经典P 205 与训练指南P 332 有关于Bellman_Ford算法的介绍和代码. 其实SPFA算法就是Bellman_Ford算法的(加上了判负圈的)队列实现版本.

下面给出3种Bellman_Ford算法的实现代码:

1.Bellman_Ford简单版

//Bellman_Ford算法简单形式
//求的是从0点到其他点的单源最短路径,复杂度O(n*m)

void Bellman_Ford()
{
    for(int i=0;i<n;i++) d[i]=INF;
    d[0]=0;
    for(int k=0;k<n-1;k++)  //迭代n-1次
    for(int i=0;i<m;i++)    //检查每条边
    {
        int x=u[i],y=v[i];
        if(d[x]<INF) d[y] =min(d[y],d[x]+w[i]); //松弛
    }
}

2.Bellman_Ford队列版

//Bellman_Ford算法队列实现
//求的是从0点到其他点的单源最短路径,复杂度O(n*m)

void Bellman_Ford()
{
    queue<int> q;
    bool inq[maxn];
    for(int i=0;i<n;i++) d[i]= i==0?0:INF;
    memset(inq,0,sizeof(inq));
    q.push(0);

    while(!q.empty())
    {
        int x=q.front(); q.pop();
        inq[x]=false;
        for(int e=first[x];e!=-1;e=next[e])
        if(d[v[e]]> d[x]+w[e])
        {
            d[v[e]] = d[x]+w[e];
            if(!inq[v[e]])
            {
                inq[v[e]]=true;
                q.push(v[e]);
            }
        }
    }
}

3.Bellman_Ford标准版_SPFA

//Bellman_Ford刘汝佳模板_SPFA(能判负圈)
//求的是从s点到其他点的单源最短路径,复杂度O(k*e)

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define INF 1e9

struct Edge
{
    int from,to,dist;
    Edge(int f,int t,int d):from(f),to(t),dist(d){}
};

struct BellmanFord
{
    int n,m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool inq[maxn];     //是否在队列中
    int d[maxn];        //s到各个点的距离
    int p[maxn];        //最短路中的上一条弧
    int cnt[maxn];      //进队次数

    void init(int n)
    {
        this->n=n;
        for(int i=0;i<n;i++) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from,int to,int dist)
    {
        edges.push_back(Edge(from,to,dist));
        m = edges.size();
        G[from].push_back(m-1);
    }

    bool negativeCycle(int s)
    {
        queue<int> Q;
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;i++) d[i]=INF;
        inq[s]=true,d[s]=0,Q.push(s);

        while(!Q.empty())
        {
            int u=Q.front(); Q.pop();
            inq[u]=false;
            for(int i=0;i<G[u].size();i++)
            {
                Edge &e=edges[G[u][i]];
                if(d[e.to] > d[u]+e.dist)
                {
                    d[e.to] = d[u]+e.dist;
                    p[e.to] = G[u][i];
                    if(!inq[e.to])
                    {
                        Q.push(e.to);
                        inq[e.to]=true;
                        if(++cnt[e.to]>n) return true;
                    }
                }
            }
        }
        return false;
    }
}BF;

4.Bellman_Ford快速版_SPFA(内存消耗多)

//POJ1511题用到,用邻接表实现,避免了vector添加边信息的时间消耗
#include<algorithm>
#include<vector>
#include<queue>
#define INF 1e9
using namespace std;
const int maxn =1000000+10;
int n,m;

struct Edge
{
    int from,to,dist;
    Edge(){}
    Edge(int f,int t,int d):from(f),to(t),dist(d){}
};

struct BellmanFord
{
    int n,m;
    int head[maxn];     //每个节点邻接表的头
    int next[maxn];
    Edge edges[maxn];   //所有的边信息
    bool inq[maxn];
    int d[maxn];
    int p[maxn];
    int cnt[maxn];

    void init(int n)
    {
        this->n=n;
        this->m=0;
        memset(head,-1,sizeof(head));
    }

    void AddEdge(int from,int to,int dist)
    {
        edges[m]=Edge(from,to,dist);
        next[m]=head[from];
        head[from] = m++;
    }

    bool negativeCycle(int s)
    {
        queue<int> Q;
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;i++) d[i]= i==s?0:INF;
        Q.push(s);

        while(!Q.empty())
        {
            int u=Q.front(); Q.pop();
            inq[u]=false;
            for(int i=head[u];i!=-1;i=next[i])
            {
                Edge &e=edges[i];
                if(d[e.to] > d[u]+e.dist)
                {
                    d[e.to] = d[u]+e.dist;
                    p[e.to] = i;
                    if(!inq[e.to])
                    {
                        inq[e.to]=true;
                        Q.push(e.to);
                        if(++cnt[e.to]>n) return true;
                    }
                }
            }
        }
        return false;
    }
}BF1,BF2;