一、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<iostream>
#include<cstring>
#include<queue>
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);
queue<int>q;
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;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
if(SPFA())cout<<dis[n]<<endl;
else puts("impossible");
}
逐行分析：
SPFA的平均时间复杂度是O(Km)，m为边数，K为每个点的平均入队次数。这是相当高效的！
该效率甚至超过了堆优化版的dijkstra算法。但是，这个算法能够取代dijkstra吗？
答案是不能的。
在最坏情况下，即每个点入队n次。**那么此时的时间复杂度是O(mn)**这个时间复杂度就是相当高了，而堆优化的dijkstra是O(mlogn)。
三、SFPA解决负环问题：
1、什么是负环？
上述这个环每走一圈，最短路 - 2 。因此，我们可以围着这个圈旋转无数次，那么我们的最短路就到负无穷了。因此，这种情况是没有最短路的。
2、如何判断负环？
存在最短路的话，一定是没有与源点相通的负环的，那么我们此时从源点引出的最短路经过的边长最多为n-1。
为什么？
假设这是一个图，那么这个环是每走一圈都会回到C点，而每走一圈，路程＋4。那么从最上面的点，到最后一个点的最短路一定是不走这个环的。所以我们的最短路是一条线。
而一条线上，n个点之间的边是n-1。所以图中所有最短路的边数最多是n-1。如果存在负环，那么它为了减少路程必定会进环，因此此时的边数必定是大于等于n的。
而这就是我们判断负环的依据：最短路径上经过的边大于等于n。
因此，我们只需要在SPFA的算法中，加上一个数组，来存储最短路的边数即可。
3、细节处理：
这个图中的确存在负环，但是我们的S点出发的最短路不经过这个负环。那么我们的算法在这种情况下就失效了。因此。我们让所有点都进队，此时负环中的点必定也会进队。
因此必定会找到这个负环。我们把dis数组全部初始化为正无穷。那么当遇到一个负权边的时候，必定能够松弛成功，因为w是负的，dis又都是正无穷。也就是说我们的dis数组初始值是多少不重要，因为不管你初始化为多少，我给你减去一个数，你必定减小，必定松弛成功。接着它就会围绕这个环不断地转，当走过的边数是n的时候，就是负环了。
4、模板：
（1）问题：
文章来源：https://www.toymoban.com/news/detail-430937.html
（2）模板：
#include<iostream>
#include<cstring>
#include<queue>
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);
queue<int>q;
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");
}
（3）分析：
由于我们一开始入队一个，就是找一个点的最短路，入队n个点那么就是找n个点的最短路，所以此时的最坏时间复杂度是：O(mn2)。这个方式是相当低效的。文章来源地址https://www.toymoban.com/news/detail-430937.html
到了这里，关于第十八章 SPFA算法以及负环问题（利用dijkstra推导出该算法，超级详细！！）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
