第十八章 SPFA算法以及负环问题

• 一、dijkstra算法的弊端
• 二、dijkstra算法的优化
• • 1、SPFA算法
  • • （1）算法思路：
    • （2）算法模板：
    • • 问题：
      • 模板：
      • 逐行分析：
• 三、SFPA解决负环问题：
• • 1、什么是负环？
  • 2、如何判断负环？
  • 3、细节处理：
  • 4、模板：
  • • （1）问题：
    • （2）模板：
    • （3）分析：

一、dijkstra算法的弊端

我们回顾一下之前的dijkstra算法的证明过程。如果大家没看过之前的dijkstra算法的简易证明的话，作者在这里建议先去看一下。
传送门：
第十六章 Dijkstra算法的讲解以及证明（与众不同的通俗证明）
那么假设你已经看过这篇文章，我们发现，我们将每次松弛操作后的最小距离定义为已经确定的最短路。那么我们的前提就是：

该公式中的W是正数。那么我们利用一下极限思想，假设存在一个W是负无穷。那么右端的值就是负无穷。此时我们就还能够更新我们的最短路。

因此当我们的图中存在负权边的时候，我们的dijkstra算法是不一定成立的。

那么我们如何基于这种情况对于dijkstra算法进行优化呢？

我们下列的优化是基于之前的优先队列优化过的dijkstra算法，所以如果屏幕前的同学不懂优先队列优化的dijkstra算法的话，建议再去看一下前面的一篇文章：

第十七章 优先队列优化Dijkstra算法

二、dijkstra算法的优化

1、SPFA算法

（1）算法思路：

作者不会在这里直接甩出一个算法让大家硬背。我们看看我们能不能自己推导出SPFA算法呢？

由于负权边的存在，我们不能再保证每次松弛过后的最小值是最短路，解决这个事情很简单。既然你不一定是最短路，那我就接着松弛你喽。只要你无法再松弛了，那必定是最短路了。

既然我们无法保证最小的那个是最短路了，那我们还有必要去选出最小值吗？

答案是没必要的，因为选出最小值不仅无法做到确定最值，还白白增加了时间复杂度。所以我们不再需要优先队列存储，只需要最简单的队列即可。

所以我们的第一个改变就是：不再选出最小值。

接着，那我们怎么知道所有点都无法再继续松弛了呢？此时，我们发现，我们之前在实现优化的dijkstra算法的时候，我们只让松弛过后的点进队列。所以，如果不再入队了，那么就说明这个点无法松弛了，也就是说找到了最短路。因此，当队列为空的时候，就说明已经所有点的最短路都找到了。

这里需要注意两个细节：

出队之后的点还能入队吗？

在我们优化dijkstra的算法中，我们出队的是最小点，此时这个点的最短路确定了，所以不再入队。但是，现在来看，我们的点即使出队了，但依旧无法确定是最小路径，因为你不知道这个点能够利用当前的路再去松弛，因此，出队的点依旧能够再次进队。

接着我们看下面这个例子，再去解决下一个细节。

我们让第一个点入队，然后让这个点去松弛剩下的点，那么松弛成功的应该是1的邻接点：2，3，5。（证明请看dijkstra算法的文章）
同时也说明，我们此时依旧只需要去松弛邻接点。
此时队列中的元素如下：

那么接着我们让2出队，去继续松弛。
假设我们2的邻接点都松弛成功了。

那么此时的队列中，我们惊奇的发现，5进队了两次。好，问题来了，

一个点有没有必要在队列中出现N次？

我们依旧采取前面两篇文章的风格，不主观判断，我们客观分析，那么客观分析的依据就是公式：

我们先来分析一下：
我们松弛过后，改变的数据是对应点的dis数组，第一个改变后，dis[5]=C1 改变了，当我们再次松弛成功后，dis[5]=C2又发生了改变。
那么当我们第一个d[5]出队列的时候，用的dis[5]是哪个值？答案肯定是C2。因为dis[5]对应的就是一块空间。只不过当2出队前，是C1。2出队后，是C2。也就是说，我们第一个5出队的时候，用的是C2这个数据。
我们第一个5出队的时候，利用这个公式d[U]<=C2+w去松弛了一遍。然后，轮到我们第二个5出队的时候，又利用d[U]<=C2+w去松弛一遍。即两次我们重复了。

因此，某个点无需多个同时存在于队列中。

最后，我们总结一下我们的优化思路：

不断的松弛邻接点，松弛成功的点入队，直到队列为空，说明最短路已经全部找到，其中有两个细节：一是出队的点可以再次入队，二是某个点只需要在队列中同时存在一个。

那么这就是SPFA的算法逻辑！！

恭喜你，自己优化出了一个新的算法！

如果屏幕前的你出生够早，这个算法必定是由你命名的(^ _ ^)。

（2）算法模板：

问题：

模板：

#include
#include
#include
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N],w[N],idx;
int dis[N];
bool st[N];
int n,m;
void add(int x,int y,int z)
{e[idx]=y,ne[idx]=h[x],w[idx]=z,h[x]=idx++;
}
bool SPFA()
{memset(dis,0x3f,sizeof dis);queueq;q.push(1),dis[1]=0;st[1]=true;while(!q.empty()){int t=q.front();q.pop();st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){if(dis[e[i]]>dis[t]+w[i]){dis[e[i]]=dis[t]+w[i];if(!st[e[i]])q.push(e[i]);st[e[i]]=true;}}}if(dis[n]>0x3f3f3f3f/2)return false;else return true;   
}int main()
{memset(h,-1,sizeof h);cin>>n>>m;for(int i=0;iint a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}if(SPFA())cout<

#include
#include
#include
using namespace std;
const int N=1e5+10;
int h[N],e[2*N],ne[2*N],w[2*N],idx;
bool st[N];
int dis[N],cnt[N];
int n,m;
void add(int x,int y, int d)
{e[idx]=y,ne[idx]=h[x],w[idx]=d,h[x]=idx++;
}bool spfa()
{memset(dis,0x3f,sizeof dis);queueq;for (int i = 1; i <= n; i ++ ){st[i] = true;q.push(i);}while(!q.empty()){auto top=q.front();q.pop();st[top]=false;for(int i=h[top];i!=-1;i=ne[i]){if(dis[e[i]]>dis[top]+w[i]){dis[e[i]]=dis[top]+w[i];cnt[e[i]]=cnt[top]+1;if(cnt[e[i]]>=n)return true;if(!st[e[i]]){q.push(e[i]);st[e[i]]=true;}}}}return false;
}
int main()
{memset(h,-1,sizeof h);cin>>n>>m;while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}if(spfa())puts("Yes");else puts("No");}