SPFA算法求最短路和判断负环（支持负权边）

地址:

判断负环

描述：

思路：

1、什么是spfa算法？

stu[N]数组的区别

2、spfa算法步骤

判断负环解题思路：

代码：

判断负环：

https://www.acwing.com/problem/content/853/

https://www.acwing.com/problem/content/description/854/

判断负环：

SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA一般情况复杂度是O(m)O(m) 最坏情况下复杂度和朴素 Bellman-Ford 相同，为O(nm)O(nm)。

bellman-ford算法操作如下：

spfa算法对第二行中所有边进行松弛操作进行了优化，原因是在bellman—ford算法中，即使该点的最短距离尚未更新过，但还是需要用尚未更新过的值去更新其他点，由此可知，该操作是不必要的，我们只需要找到更新过的值去更新其他点即可。

Bellman_ford算法会遍历所有的边，但是有很多的边遍历了其实没有什么意义，我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新；因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点。

1] Dijkstra算法中的st数组保存的是当前确定了到源点距离最小的点，且一旦确定了最小那么就不可逆了(不可标记为true后改变为false)；SPFA算法中的st数组仅仅只是表示的当前发生过更新的点，且spfa中的st数组可逆(可以在标记为true之后又标记为false)。顺带一提的是BFS中的st数组记录的是当前已经被遍历过的点。 2] Dijkstra算法里使用的是优先队列保存的是当前未确定最小距离的点，目的是快速的取出当前到源点距离最小的点；SPFA算法中使用的是队列(你也可以使用别的数据结构),目的只是记录一下当前发生过更新的点。

例子

queue a>>b>>c; add(a,b,c); } spfa(); return 0; } 判断负环： #include #include #include using namespace std; queueq; const int N=1e4+10; int h[N],e[N],ne[N],w[N],idx; bool stu[N]; //dist存放从1~x号节点的最短距离，cnt[N]存放从1~x号节点中的边数 int dist[N],cnt[N]; int n,m; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } bool spfa(){ dist[1]=0; //将n个节点全部加入队列，仅仅把1节点加入的化，它可能不走有负环的路 for(int i=1;idist[temp]+w[i]){ dist[j]=dist[temp]+w[i]; cnt[j]=cnt[temp]+1; //不一定要cnt[n]>=n只要有一个节点边数超过n，就说明有负环 if(cnt[j]>=n) return true; if(!stu[j]){ stu[j]=true; q.push(j); } } } } return false ; } int main(){ cin>>n>>m; memset(h,-1,sizeof h); memset(dist,0x3f,sizeof dist); for(int i=0;i>a>>b>>c; add(a,b,c); } if(spfa()) cout