首页 文章

关于贝尔曼福特的询问

提问于
浏览 次
-2

我最近一直在研究贝尔曼福特算法 . 我怀疑如果有源图中的负权重周期可以从源顶点到达，那么对于所有节点或某些节点都不存在最短 . 这是我的Bellman ford实现 .

//O(VE)
 #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sl(n) scanf("%lld",&n)
#define pl(n) printf("%lld",n)
#define MOD 1000000007
#define inf 1e18
#define rep(i,n) for(i=0;i<n;i++)
#define mset(x,v) memset(x, v, sizeof(x))
vector<ll>t,s;
ll nodes, edges;

void bellman_ford(vector<pair<ll,ll> >mp[],ll src){
ll i,j;
for(i=1;i<=nodes;i++){
t[i]=inf;
}
t[src]=0;

vector<pair<ll,ll> > :: iterator it;

for(i=1;i<nodes;i++){//O(nodes-1) times
    for(j=1;j<=nodes;j++){//O(edges)
        if(t[j]!=inf)
        for(it=mp[j].begin();it!=mp[j].end();it++)
        t[it->first]=min(t[j]+it->second,t[it->first]);
    }
}

bool flag=1;
for(j=1;j<=nodes;j++){//detecting negative cycles
    for(it=mp[j].begin();it!=mp[j].end();it++)
    if(t[j]+it->second < t[it->first])
        {
            flag=0;break;
        }

}

if(flag==0)
for(j=1;j<=nodes;j++){//assigning all shortest paths to be -inf
        t[j]=-inf;
}


}


int main()
{
ll x, y, wt,i;
sl(nodes);
sl(edges);
vector<pair<ll,ll> >mp[nodes+1];//1 based indexing of nodes
t.resize(nodes+1);

rep(i,edges){
sl(x);sl(y);sl(wt);
mp[x].push_back(make_pair(y,wt));
mp[y].push_back(make_pair(x,wt));
}

ll src;sl(src);
bellman_ford(mp,src);


for(i=1;i<=nodes;i++)
cout<<i<<" "<<t[i]<<endl;
}
c++ graph-theory shortest-path bellman-ford

1 回答

  • 0

    那么，AFAIK网络中没有最短路径，如果网络包含负循环，因为它会进入无穷大 . BellmanFord只有在没有负循环的情况下才能工作，如果存在则能够找到它 . 然而，你的C有点可怕 . 事实证明，之后

    for(i=1;i<nodes;i++){//O(nodes-1) times
for(j=1;j<=nodes;j++){//O(edges)
    if(t[j]!=inf)
    for(it=mp[j].begin();it!=mp[j].end();it++)
    t[it->first]=min(t[j]+it->second,t[it->first]);
}
}

    如果没有负循环（可以提前终止），则算法终止 .

    如果在该循环之后存在t [j] it-> second <t [it-> first]的边沿，则存在负循环 . 如果这是你的问题，那么你可能在错误的论坛 . 如果您的代码是正确的实现，我的explenation工作 .

    回复于

相关问题