看來一千個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

總結

以上是生活随笔為你收集整理的Bellman-Ford的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。