spfa 判断负环 (转载)

当然,对于Spfa判负环,实际上还有优化:就是把判断单个点的入队次数大于n改为:如果总的点入队次数大于所有点两倍

时有负环,或者单个点的入队次数大于sqrt(点数)有负环。这样时间复杂度就降了很多了。

判断给定的有向图中是否存在负环。

利用 spfa 算法判断负环有两种方法:

1) spfa 的 dfs 形式,判断条件是存在一点在一条路径上出现多次。

2) spfa 的 bfs 形式,判断条件是存在一点入队次数大于总顶点数。

代码如下:

法 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 ++;

}文章来源地址https://www.yii666.com/article/756151.html

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]) {            //存在一点在一条路径上出现多次

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));文章地址https://www.yii666.com/article/756151.html

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>网址:yii666.com<

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()) {文章来源地址:https://www.yii666.com/article/756151.html

u = q.front();网址:yii666.com

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;                //存在一点入队次数大于总顶点数

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;

}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png