首页 > 代码库 > 再谈Bellman-Ford
再谈Bellman-Ford
这几天学校女生节，挺累的，感觉还是挺好玩的，前几天看了一下最短路，Bellman-fort算法果然比较厉害，今天又参考了刘汝佳的两本书，有了一点新的认识。
废话不说，先上代码：
#include <bits/stdc++.h>using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1000;struct Edge{ int from,to; int dist;};struct BellmanFord{ int n,m; vector<Edge> edges; vector<int> G[maxn]; bool inq[maxn]; int 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,int dist) { edges.push_back((Edge) { from,to,dist }); m = edges.size(); G[from].push_back(m-1); } bool negativeCycle(int s) { queue<int> Q; memset(inq,0,sizeof(inq)); memset(cnt,0,sizeof(cnt)); for(int i=0; i<n; i++) { d[i] = INF; } d[s] = 0; inq[s] = true; Q.push(s); 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[u]<INF&&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 false; } } } } return true; }};struct BellmanFord{ int n,m; vector<Edge> edges; vector<int> G[maxn]; bool inq[maxn]; int 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,int 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; }};
第一个Bellman-Ford算法是紫书上的；
解析：
1、起点入队列
2、初始化点到起点的距离是INF；
3、和Dijkstra相比，每个结点可以多次加入（如果有负环，那么这个结点是可以多次松弛的，一旦次数无穷就说明了这的确是个负环）；
4、因为是从起点出发的，然后在搜索邻接表，没有找到负环，只能说明，从起点到不了负环，但是可能是有负环的。没有负环，最短路数组 d 是正确可用的。
第二个Bellman-Ford算法是白书上的；
解析：
1、Bellman-Ford 算法一个重要应用就是判负环，上面的一个起点入队列，就要改成所有点入队列。
2、初始化 d 数组为 0：
可以从第二图中，有一个负环，但是从 0 ，无法松弛；但是，在队列中，从 1 开始搜索的时候，还是可以松弛，并且找到这个负环；然后由于每个结点之前都入过队列，就能保证找到那个负环。
再谈Bellman-Ford
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。