浅谈SPFA及其优化
- SPFA的前提-----Bellman-Ford算法
- SPFA的核心思想
- SPFA详解
- SPFA的优化
- 图中负环的判断
一、Bellman-Ford算法
Bellman-Ford 算法是一种用来求单源最短路径的一种算法，可以用于负边权上，但是如果有负环的话就没办法了（有负环可能算的出来吗？） 优点：便于理解，代码简短； 缺点：时间复杂度较高（保证为VE（边数*点数）），容易TLE，要仔细注意题的数据范围Bellman-Ford算法的核心操作就是松弛，如果dis [ i ] + length [ i ] [ j ] < dis [ j ] ,就用dis [ i ] + length [ i ] [ j ] 更新dis [ j ] ；
算法步骤，枚举每个点，用每条边对其进行松弛操作，使答案不断逼近最优解，运行V-1次结束
算法正确性证明请参考 核心代码for(int i=1;i<=n-1;i++){ for(int j=1;j<=m;j++) { if(dis[u[j]]+val[j] 当然我们可以考虑一个小优化，当循环到某个点i时已经无法松弛的时候，直退出循环
优化后的代码
for(int i=1;i<=n-1;i++){ int flag=0; for(int j=1;j<=m;j++) { if(dis[u[j]]+val[j] < dis[v[j]]) { dis[v[j]]=dis[u[j]]+val[j]; flag=1;//判断是否已经松弛完了 } } if(flag==0) break;//松弛完了就直接退出，小优化； } SPFA的思想
其实在国外并不承认SPFA，只是将这个算法称作队列优化的Bellman-Ford算法，其实也是显而易见的，但是因为在中国，SPFA算法的发明者段凡丁是独自发现的，其实在国外早就有了类似的优化 SPFA的思想其实很简单，从起点开始向其他点进行松弛，并把松弛后的点加入队列中，这样对所有点进行松弛，SPFA复杂度在随机数据下的复杂度约为O（kE）（k是一个很小的常数） 但在最坏情况下，SPFA的复杂度任仍下降到O（VE），所以在正权图中更推荐效率更高的dijkstra算法（当然如果dijkstra算法超时的话也只能用SPFA了）但SPFA和Bellman-Ford算法一样可以在负边上运行。SPFA详解+代码（丑的话不要介意）
SPFA大概的算法步骤已经有所介绍了，就是从起点开始按照深度对每个点进行松弛操作，将松弛后的点逐个加入队列里，当队列里所有点都已经操作后便结束算法；核心代码如下
inline void spfa(int s){ fill(dis+1,dis+n+1,2147483647); memset(vis,false,sizeof(vis)); dis[s]=0,que[1]=s,vis[s]=true; int head=0,tail=1,u; while(head SPFA的小优化
SPFA主要有两种优化策略，SLF和LLL，介绍引自百度百科SPFA算法有两个优化策略SLF和LLL——SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)< dist(i)，则将j插入队首，否则插入队尾； LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出队进行松弛操作。SLF 和 LLF 在随机数据上表现优秀，但是在正权图上最坏情况为 O(VE)，在负权图上最坏情况为达到指数级复杂度。
按照个人经验，随机数据下两种优化的效率大概为25%~40%左右，
实现较为简单，就不想贴代码了；图中负环的判断
Bellman-Ford的判别方法很简单，对所有点松弛完后，再枚举所有边，如果有一条边仍能被松弛，那么说明图中有负环
代码
inline void bell(){ for(int i=1;i<=n-1;i++)//松弛操作 { int zgs=0; for(int j=1;j<=m;j++) { if(dis[u[j]]+val[j] dis[u[i]]+val[i]) { falg=0; break; } }} 而对于SPFA来说，一般有两种判断负环的方法
1、记录每个点入队的次数，如果某个点超过了N次，则存在负环
2、记录每个路径经过点的数量，如果存在某条路径经过的点的数量超过了N次，那么也说明存在负环相比较而言，个人更偏向与第二种方法，实际数据对比的话第二种方法要比第一种方法要快那么一些，所以更偏向第二种方法