Bellman-Ford&&SPFA

Bellman-Ford：

bool bellman(int v0)
{
    int i,j;
    for(i=1;i<=nv;i++) d[i]=maxx;
    d[v0]=0;
    for(i=1;i<nv;i++)//n个顶点 
    {
        for(j=1;j<=ne;j++)//m条边 
        {
            if(d[edge[j].a]+edge[j].w<d[edge[j].b])//负权回路 
                d[edge[j].b]=d[edge[j].a]+edge[j].w;
        }
    }
    for(j=1;j<=ne;j++)
        if(d[edge[j].a]+edge[j].w<d[edge[j].b]) return false;
    return true;
}

spfa:

void spfa(){
    memset(d,0x3f,sizeof d);//dist数组 
    meeset(v,0,sizeof v);//是否在队列中 
    d[1]=0,v[1]=1;
    q.push(1);
    while(!q.empty())
    {
        int x=q.front();q.pop();//取出队头 
        v[x]=0;
        for(int i=head[x];i;i=nxet[i])//扫描所有出边 
        {
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;//更新，把新的二元组插入队列 
                if(!v[y]) q.push(y),v[y]=1;
            }
        }
    }
}