-2

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

 //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;
}
4

1 回答 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] 的边，那么就有一个负循环。如果这是你的问题，那么你可能是在错误的论坛。仅当您的代码是正确的实现时，我的解释才有效。

于 2016-03-21T16:12:24.370 回答