spfa，让人又爱又恨的单源最短路算法

建图和前一篇博客一样，还是一样的题，有需求的自行跳转

image.png

看完前两篇估计大家都对最短路有一个比较清晰的认识了，直接上代码加注释

len数组依旧是起点到各点的最短距离，通过不断更新，最终这就是最终答案

used数组用于判断某点在不在队列当中

先说一下spfa的大体思路，给定起点后，把起点入队，以队首（此时为起点）为中转点更新所有与起点直接相连的点的距离，如果更新成功（或者说松弛成功）并且此点不在队列中（利用used判断），就将其入队，此时将队首出队，因为他已经松弛过和他相连的点了，可以舍弃了，然后在对队首元素作同样的操作，直到队列所有元素出队，代表无可更新，此时就是最短路了

仔细想想，像不像一张巨大的蜘蛛网从起点开始扩散，直到扩散到所有点不停更新啊hhhhh

解释一些小细节，首先spfa的元素是可能再次入队的（不同于dji），这很好理解，假设v点曾经进过队并且现在已经出队，因为我在bfs的过程中再次发现比当前len v更小的值，我自然要松弛更新，把v再次入队，因为len v变了导致以v为中转的那些点又有了被更新以及再次入队的可能性，这也保证了spfa没有遗漏任意一种可能

for(int i=1;i<n+1;i++){

len[i]=2147483647;//初始化len全为超大值，代表不可到达

}

len[s]=0;//自己到自己为0

queue<int>dui;//建立队列

dui.push(s);//起点入队

used[s]=1;//标记起点入队

while(!dui.empty())//只要还没空

{

int u=dui.front();//把队首给提出来

dui.pop();//这个元素我们用u保存了，他可以出队了

used[u]=0;//标记此点出队

for(int i=head[u];i;i=bian[i].qian){//遍历与u相连的边

int v=bian[i].wei;

if(len[v]>len[u]+bian[i].quan){//如果能更新，就更新，这里额外说明，即使松弛成功也不代表一定会入队，因为一个点可能会多次被松弛，如果他已经在队里了，就没有必要多此一举，如果此时都入队虽然正确性没有问题，但是效率大大降低，队里有一个此元素就够了，只需要把len v更新就可

len[v]=len[u]+bian[i].quan;

if(!used[v])

{

dui.push(v);//如果没进队，就进队

used[v]=1;//标记进队

}

}

}

}//算法结束

大家应该也看出来为啥spfa可以计算负权了吧，因为他在更新到更小的路径的时候，会用这个点接着更新他旁边的点，所以是可以处理负权的，spfa的本质是动态规划，是搜索，而DJi是贪心
另外一说，我并不会证明spfa的复杂度。。。spfa的复杂度我在大部分使用的时候都是和优化后的DJI一个水平，除了一些题目会故意卡spfa，注意！SPFA很容易被卡，同样是因为他找到一个更小路径就要跳到之前更新的问题，比如现在有很多点，你开始就把v3给更新了，当你不停更新更新到v1000的时候发现v1000可以更新v3，然后你还得从v3又开始更新之前的过程。。。就因为len v3的改变，你之前的更新都白费劲了，简直是当场炸裂，一些比较特殊的图会出现上述情况，一旦数据很离谱（出题人故意出这种数据），SPFA就会炸掉，所以还是建议SPFA和堆优化的DJI都掌握啦！

SPFA完

最后编辑于：2019.12.26 22:32:40