看来一千个acmer有一千个迪杰斯特拉,Bellman-Ford也是一样。
看了刘汝佳的bellman-ford,简直和spfa一模一样啊!!!
松弛n -1 次还是可以松弛,说明有负环;
刘汝佳写得很有水平,学习了。每个点都有可能从这个点出发找到负环,都入队列,相互间分开,找第一个点,找到负边,入对列,原来的点出队列,下次有可能还用到;该点不是最优的。要搜索该点。下次同等级别的点找到该点,就不用push到队列中了!!!
当下次还可以通过其他点松弛他cnt++;他又被松弛了;如果他被松弛了好多好多次(n-1);这样下去的只能说明一个问题:已经没有最短路,有的只是一个负圈;因为,既然可以通过好多好多点通过这个点继续找到更近的路,而这些点早可以够成了一条最短路了,什么情况这个点可以被松弛好多好多次呢,就是这个点存在于一个负圈里面,其他点到这个点转一圈 d 又减小了;
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000;
struct Edge
{
int from,to;
double dist;
};
struct BellmanFord
{
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
double d[maxn];
int p[maxn];
int cnt[maxn];
void init(int n)
{
this->n = n;
for(int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, double dist)
{
edges.push_back((Edge)
{
from, to, dist
});
m = edges.size();
G[from].push_back(m-1);
}
bool negativeCycle()
{
queue<int> Q;
memset(inq, 0, sizeof(inq));
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < n; i++)
{
d[i] = 0;
inq[0] = true;
Q.push(i);
}
while(!Q.empty())
{
int u = Q.front();
Q.pop();
inq[u] = false;
for(int i = 0; i < G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
if(d[e.to] > d[u] + e.dist)
{
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
if(!inq[e.to])
{
Q.push(e.to);
inq[e.to] = true;
if(++cnt[e.to] > n) return true;
}
}
}
}
return false;
}
};
原文链接: https://www.cnblogs.com/TreeDream/p/6111387.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/244760
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!