个人网站和企业网站区别/安卓优化大师老版本

 算法同利用SPFA算法求单源点最短路径一致

SPFA算法：找单源点最短距离_可惜浅灰的博客-CSDN博客

再此基础上增加了sum数组，用于统计各个结点的入队次数，只要发现有结点的出队次数不小于结点总数，则有负环；反之，若算法函数运行结束后仍然没有结点的入队次数不小于结点总数，则没有负环。

代码实现：

#include <iostream>
#include <queue>
using namespace std;
#define maxn 100int n, m;
int dis[maxn];
int head[maxn], cnt;
bool ins[maxn];
int sum[maxn];class Edge
{
public:int to;int weight;int next;
};
Edge edge[maxn << 1];void InsertEdge(const int& u, const int& v, const int& w)
{edge[++cnt].to = v;edge[cnt].weight = w;edge[cnt].next = head[u];head[u] = cnt;
}void CreateGreph()
{int u, v, w;cout << "请输入结点数：" << endl;cin >> n;cout << "请输入边数：" << endl;cin >> m;cout << "请依次输入每条边的两个顶点和权值：" << endl;for (int i = 1; i <= m; i++){cin >> u >> v >> w;InsertEdge(u, v, w);}
}bool SPFA(int u)
{queue<int> q;memset(dis, 0x3f3f3f3f, sizeof(dis));q.push(u);dis[u] = 0;ins[u] = true;sum[u]++;while (!q.empty()){int x = q.front();q.pop();ins[x] = false;for (int i = head[x]; i; i = edge[i].next){int v = edge[i].to;if (dis[v] > dis[x] + edge[i].weight){dis[v] = dis[x] + edge[i].weight;if (!ins[v]){if (++sum[v] >= n){return true;}q.push(v);ins[v] = true;}}}}return false;
}void Print()
{for (int i = 1; i <= n; i++){cout << dis[i] << " ";}cout << endl;
}int main()
{CreateGreph();if (SPFA(1)){cout << "有负环" << endl;}else{cout << "没有发现负环" << endl;}//Print();return 0;
}