——Bellman-Ford

初始状态：

0 inf inf ... inf inf

for(int i = i ; i<= n; i++) dis[i] = inf;
dis[1] = 0;
 
for(int k = 1; k <= n-1; k++){//次数为顶点数减一
    for(int i = 1; i <= m ; i++){//边数
        if(dis[u[i]] != inf&&dis[v[i]] > dis[u[i]] +w[i]){//这里有个一开始设置为无限的值，应先进行判断再进行比较 
            dis[v[i]] = dis[u[i]] + w[i];
        }
    }
}
flag = 0;
//结束后再进行一轮以检测是否有负权回路 
for(int i = 1; i <=m ; i++)
    if(dis[v[i]] > dis[u[i]] + w[i]) flag = 1;
if(flag == 1) printf("此图含有负权回路"); 

模板：1

/*
*  单源最短路bellman_ford算法，复杂度O(VE)
*  可以处理负边权图。
*  可以判断是否存在负环回路。返回true,当且仅当图中不包含从源点可达的负权回路
* vector<Edge>E;先E.clear()初始化，然后加入所有边
*  点的编号从1开始(从0开始简单修改就可以了)
*/
const int INF=0x3f3f3f3f;
const int MAXN=550;
int dist[MAXN];
struct Edge
{
    int u,v;
    int cost;
    Edge(int _u=0,int _v=0,int _cost=0):u(_u),v(_v),cost(_cost){}
};
vector<Edge>E;
bool bellman_ford(int start,int n)//点的编号从1开始
{
    for(int i=1;i<=n;i++)dist[i]=INF;
    dist[start]=0;
    for(int i=1;i<n;i++)//最多做n-1次
    {
        bool flag=false;
        for(int j=0;j<E.size();j++)
        {
            int u=E[j].u;
            int v=E[j].v;
            int cost=E[j].cost;
            if(dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                flag=true;
            }
        }
        if(!flag)
            return true;//没有负环回路
    }
    for(int j=0;j<E.size();j++)
        if(dist[E[j].v]>dist[E[j].u]+E[j].cost)
            return false;//有负环回路
    return true;//没有负环回路
}

模板2:FIFO队列优化

Spfa是Bellman-Ford算法利用队列的优化，Bellman-Ford算法存在大量的无效松弛，spfa对它进行改进，对于每个点只松弛与这个点相关的边。

image

该优化和Dijkstra算法很相似，一方面，优先队列替换成了普通的FIFO队列，另一方面，一个结点可以多次进入队列。

/*
*  单源最短路SPFA
*  时间复杂度  0(kE)
*  这个是队列实现，有时候改成栈实现会更加快，很容易修改
*  这个复杂度是不定的
*/
const int MAXN=1010;
const int INF=0x3f3f3f3f;
struct Edge
{
int v;
int cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w)
{
E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//在队列标志
int cnt[MAXN];//每个点的入队列次数
int dist[MAXN];
bool SPFA(int start,int n)
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
        dist[i]=INF;
    vis[start]=true;
    dist[start]=0;
    queue<int>que;
    while(!que.empty())
        que.pop();
    que.push(start);
    memset(cnt,0,sizeof(cnt));
    cnt[start]=1;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=0;i<E[u].size();i++)
        {
            int v=E[u][i].v;
            if(dist[v]>dist[u]+E[u][i].cost)
            {
                dist[v]=dist[u]+E[u][i].cost;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                    if(++cnt[v]>n)  //cnt[i]为入队列次数，用来判定是否存在负环回路
                        return false;
                }
            }
        }
    }
    return true;
}