本文共 537 字，大约阅读时间需要 1 分钟。

BellmanFord

• 判断图中是否存在负环
• 求带有负边权的最短路
  一共进行 N - 1 次更新，每次更新都能确定源点到一个节点的最短路，如果进行N-1次循环之后还可以更新点就说明存在负环

模板

using namespace std;int inf = 0x3f3f3f3f;int dis[N], n;struct ac{
   	int u, v, c;};vector
   
     g;bool BellmanFord() {
   	mem(dis, inf);	dis[1] = 0;	for (int i = 1; i <= n; ++i) {
   		// 判断是否能更新点		// 加快判断		bool flag = false;		for (int j = 0; j < g.size(); ++j) {
   			ac t = g[j];			if (dis[t.v] > dis[t.u] + t.c) {
   				dis[t.v] = dis[t.u] + t.c;				flag = true;			}		}		// 如果不能更新点，就不存在负环		if (!flag)	return false;	}	return true;}
   

转载地址：http://jkprf.baihongyu.com/