spfa 判断负环 (转载)
當(dāng)然，對于Spfa判負環(huán)，實際上還有優(yōu)化：就是把判斷單個點的入隊次數(shù)大于n改為：如果總的點入隊次數(shù)大于所有點兩倍
時有負環(huán)，或者單個點的入隊次數(shù)大于sqrt(點數(shù))有負環(huán)。這樣時間復(fù)雜度就降了很多了。
?
判斷給定的有向圖中是否存在負環(huán)。
????? 利用 spfa 算法判斷負環(huán)有兩種方法：
????? 1） spfa 的 dfs 形式，判斷條件是存在一點在一條路徑上出現(xiàn)多次。
????? 2） spfa 的 bfs 形式，判斷條件是存在一點入隊次數(shù)大于總頂點數(shù)。
????? 代碼如下：
?
?
?
法 1 （spfa 的 dfs 形式）：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
?
const int oo = 1 << 30;
const int maxn = 1010;
?
struct Edge {
???? int u, v, t, next;
}edge[2010];
int prev[maxn], p[maxn], d[maxn];
bool vis[maxn], flag;
int tot;
?
void addEdge(int u, int v, int t) {
???? edge[tot].u = u;
???? edge[tot].v = v;
???? edge[tot].t = t;
???? edge[tot].next = prev[u];
???? prev[u] = tot ++;
}
?
void spfa(int u) {
???? int v;
????
???? for (int i = prev[u]; i != -1; i = edge[i].next) {
???????? v = edge[i].v;
?
???????? if (d[u] + edge[i].t < d[v]) {
???????????? if (vis[v]) {??????????? //存在一點在一條路徑上出現(xiàn)多次
???????????????? flag = true;
???????????????? return ;
???????????? }
???????????? else {
???????????????? d[v] = d[u] + edge[i].t;
???????????????? vis[v] = true;
???????????????? spfa(v);???
????? ???????}
???????? }
???? }
}
?
int main() {
???? //freopen("input.txt", "r", stdin);
???? //freopen("output.txt", "w", stdout);
????
???? int T;
???? int a, b, t;
???? int n, m;
?
???? scanf("%d", &T);
?
???? while (T --) {
???????? scanf("%d%d", &n, &m);
????????
???????? memset(prev, -1, sizeof(prev));
???????? tot = 0;
???????? for (int i = 1; i <= m; i ++) {
???????????? scanf("%d%d%d", &a, &b, &t);
???????????? addEdge(a, b, t);
???????? }
????????
???????? memset(vis, false, sizeof(vis));
???????? fill(d, d + n, oo);
???????? d[0] = 0;
????????
???????? flag = false;
????????
???????? spfa(0);
????????
???????? if (flag) printf("possible\n");
???????? else printf("not possible\n");
???? }
?
???? return 0;
}
?
?
?
?
法 2 （spfa 的 bfs 形式）：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
?
const int oo = 1 << 30;
const int maxn = 1010;
?
struct Edge {
???? int u, v, t, next;
}edge[2010];
int prev[maxn], p[maxn], d[maxn], in[maxn];
bool vis[maxn];
int tot;
queue<int> q;
?
void addEdge(int u, int v, int t) {
???? edge[tot].u = u;
???? edge[tot].v = v;
???? edge[tot].t = t;
???? edge[tot].next = prev[u];
???? prev[u] = tot ++;
}
?
bool spfa(int n) {
???? int u, v;
?
???? while (!q.empty()) q.pop();
???? memset(vis, false, sizeof(vis));
???? memset(in, 0, sizeof(in));
???? fill(d, d + n, oo);
????
???? d[0] = 0; vis[0] = true;
???? q.push(0);
????
???? while (!q.empty()) {
???????? u = q.front();
???????? vis[u] = false;
???????? for (int i = prev[u]; i != -1; i = edge[i].next) {
???????????? v = edge[i].v;
???????????? if (d[u] + edge[i].t < d[v]) {
???????????????? d[v] = d[u] + edge[i].t;
????????????????
???????????????? if (!vis[v]) {
???????????????????? in[v] ++;
?
???????????????????? if (in[v] > n) return true;??????????????? //存在一點入隊次數(shù)大于總頂點數(shù)
?
???????????????????? vis[v] = true;
???????????????????? q.push(v);
???????????????? }
???????????? }
???????? }
????????
???????? vis[u] = false;
???????? q.pop();
???? }
?
???? return false;
}
?
int main() {
???? //freopen("input.txt", "r", stdin);
???? //freopen("output.txt", "w", stdout);
????
???? int T;
???? int a, b, t;
???? int n, m;
?
???? scanf("%d", &T);
?
???? while (T --) {
???????? scanf("%d%d", &n, &m);
????????
???????? memset(prev, -1, sizeof(prev));
???????? tot = 0;
???????? for (int i = 1; i <= m; i ++) {
???????????? scanf("%d%d%d", &a, &b, &t);
???????????? addEdge(a, b, t);
???????? }
????????
???????? if (spfa(n)) printf("possible\n");
???????? else printf("not possible\n");
???? }
?
???? return 0;
?
}
?
總結(jié)
以上是生活随笔為你收集整理的spfa 判断负环 (转载)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： MFC消息映射的定义
- 下一篇： atitit.微信项目开发效率慢的一些总