Bellman-Ford

Bellman-Ford

BF算法求的是单源最短路问题，即每一个点到起点s的最短距离。

算法的思想在于\(d[i]=min(d[i],d[j]+e(j,i))\)

d[i]表示点i到s的最短距离，对d[i]不断进行更新，知道不能更新为止，复杂度为\(O(nm)\)

代码：

const int maxn=1e5;
struct edge{
    int u,v,w;
}e[maxn];
int d[maxn];//每个点到s的最短距离
int n,m;
void BF(int s)
{
    for(int i=1;i<=n;++i) d[i]=inf;
    d[s]=0;
    while(1)
    {
        bool update=0;
        for(int i=1;i<=m;++i)
        {
            edge now=e[i];
            if(d[now.u]!=inf&&d[now.u]+now.w<d[now.v])
                d[now.v]=d[now.u]+now.w,update=1;
        }
        if(!update) break;

    }
}

如果不存在负圈则while的循环是有限的，最多只执行n-1次，因此我们可以用下面的方法检测是否存在负圈

bool find_negative_loop(){
    mst(d,0);   //或者d[s]=0，其余为inf，这样可以顺便求出最短路
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            edge now=e[j];
            if(d[now.u]+now.w<d[now.v])
            {
                d[now.v]=d[now.u]+now.w;
                if(i==n) return true;
            }
        }
    return false;
}