首页 > 代码库 > Bellman-Ford算法
Bellman-Ford算法
Bellman-Ford可以求有负权的图的最短路，也可以判断是否有负环存在。
单源最短路模板
//从s出发到所有点的最短距离void BellmanFord(int s) { for (int i = 1; i <= n; ++i) d[i] = INF; d[s] = 0; while (true) { bool update = false; for (int i = 0; i < E; ++i) { edge e = es[i]; if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) { d[e.to] = d[e.from] + e.cost; update = true; } } if (!update) break; }}
如果没有环，最多更新n-1次，n是点的个数，如果更新了n次，证明图中有环。因为求的是最短路，所以一般判断的是负环，正环也可以判断的。
poj3259 Wormholes
求是否存在负环
#include <iostream>#include <vector>#include <cstdio>using namespace std;const int INF = 0x5f5f5f5f;const int MAX_V = 505;const int MAX_E = 2705;struct edge { int from, to, cost; };vector<edge> G;int d[MAX_V];int V, E, W;bool BellmanFord(int n){ for (int i = 1; i <= n; ++i) d[i] = INF; d[1] = 0; for (int i = 1; i <= n; ++i) { for (int j = 0; j < G.size(); ++j) { int u = G[j].from, v = G[j].to; if (d[u] != INF && d[v] > d[u]+G[j].cost) { d[v] = min(d[v], d[u]+G[j].cost); if (i == n) return true; } } } return false;}int main(){//freopen("in.txt", "r", stdin); int t; scanf("%d", &t); while (t--) { G.clear(); scanf("%d%d%d", &V, &E, &W); int u, v, w; for (int i = 0; i < E; ++ i) { scanf("%d%d%d", &u, &v, &w); G.push_back(edge{u, v, w}); G.push_back(edge{v, u, w}); } for (int i = 0; i < W; ++ i) { scanf("%d%d%d", &u, &v, &w); G.push_back(edge{u, v, -w}); } if (BellmanFord(V)) puts("YES"); else puts("NO"); } return 0;}
poj1860 Currency Exchange
求是否存在正环
//poj1860#include <iostream>#include <cstdio>#include <vector>using namespace std;const int N = 105;const int INF = 0x5f5f5f5f;struct Edge { int from, to; double rate, com;};vector<Edge> G;double d[N];bool BellmanFord(int s, double money, int n) { for (int i = 1; i <= n; ++i) d[i] = 0; d[s] = money; for (int i = 1; i <= n; ++i) { for (int j = 0; j < G.size(); ++j) { int u = G[j].from, v = G[j].to; if (d[v] < (d[u]-G[j].com)*G[j].rate) { d[v] = (d[u]-G[j].com)*G[j].rate; if (i == n) return true; } } } return false;}int main(){//freopen("in.txt", "r", stdin); int n, m; int s; double money; while (~scanf("%d%d%d%lf", &n, &m, &s, &money)) { G.clear(); while (m--) { int u, v; double r1, c1, r2, c2; scanf("%d%d%lf%lf%lf%lf", &u, &v, &r1, &c1, &r2, &c2); G.push_back((Edge){u, v, r1, c1}); G.push_back((Edge){v, u, r2, c2}); } if (BellmanFord(s, money, n)) puts("YES"); else puts("NO"); } return 0;}
Bellman-Ford的复杂度很高，可以用队列来优化（也就变成了传说中的spfa）
模板：
const int INF = 0x5f5f5f5f;const int N = 105;struct Edge { int to, cost;};vector<Edge> G[N];int cnt[N], pre[N], d[N];bool inq[N];bool BellmanFord(int s, int n) { queue<int> q; memset(inq, 0, sizeof inq); memset(cnt, 0, sizeof cnt); for (int i = 1; i <= n; ++i) d[i] = INF; d[s] = 0; inq[s] = true; q.push(s); while (q.size()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = 0; i < G[u].size(); ++i) { int v = G[u][i].to; int c = G[u][i].cost; if (d[u] < INF && d[v] > d[u] + c) { d[v] = d[u] + c; pre[v] = u; if (!inq[v]) { q.push(v); inq[v] = true; if (++cnt[v] > n) return false; // 存在负环 } } } } return true;}
poj1847 Tram
#include <iostream>#include <cstring>#include <cstdio>#include <queue>using namespace std;const int INF = 0x5f5f5f5f;const int N = 105;struct Edge { int to, cost;};vector<Edge> G[N];int d[N];bool inq[N];bool BellmanFord(int s, int n) { queue<int> q; memset(inq, 0, sizeof inq); for (int i = 1; i <= n; ++i) d[i] = INF; d[s] = 0; inq[s] = true; q.push(s); while (q.size()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = 0; i < G[u].size(); ++i) { int v = G[u][i].to; int c = G[u][i].cost; if (d[u] < INF && d[v] > d[u] + c) { d[v] = d[u] + c; if (!inq[v]) { q.push(v); inq[v] = true; } } } } return true;}int main(){//freopen("in.txt", "r", stdin); int n, s, t; while (~scanf("%d%d%d", &n, &s, &t)) { for (int i = 0; i <= n; ++i) G[i].clear(); int cnt, v; for (int i = 1; i <= n; ++i) { scanf("%d", &cnt); for (int j = 0; j < cnt; ++j) { scanf("%d", &v); G[i].push_back(Edge{v, j!=0}); } } BellmanFord(s, n); printf("%d\n", d[t]==INF ? -1 : d[t]); } return 0;}
Bellman-Ford算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。