贝尔曼算法队列优化（SPFA）

最短路问题

想必大家接触图论的时候&＃xff0c;结束了DFS和BFS&＃xff0c;接下来就是求最短路了吧&＃xff01;在学SPFA之前&＃xff0c;你也许已经接触过弗洛伊德算法和迪杰斯特拉算法&＃xff0c;甚至还学过贝尔曼算法&＃xff0c;然而&＃xff0c;不管你以前学过什么&＃xff0c;今天的SPFA都可以向你保证——零基础学会&＃xff01;
言归正传&＃xff0c;话回正题。
什么是最短路问题呢&＃xff1f;就是求两点之间的最短路&＃xff0c;当然是一个带权图&＃xff08;没权值的图还最短&＃xff1f;&＃xff09;。然而SPFA是由贝尔曼改良过来的&＃xff0c;所以这也是单源最短路的算法&＃xff08;别在意这专业的叫法&＃xff0c;真的在意就比较一下弗洛伊德算法和迪杰斯特拉算法的区别&＃xff09;&＃xff0c;可是真正的SPFA是贝尔曼的优化但不是我现在所讲的贝尔曼队列优化。但是我会习惯地称为SPFA…不要在意这奇怪的癖好。因为叫着简单。

SPFA需要用到的工具

老规矩&＃xff0c;我们用如下代码存图。

int p,s;
struct e{int u,v,dis,next;
}edge[maxm];
int head[maxm],js;
int a,b,c;


不懂邻接表的朋友们看看这个&＃xff1a;邻接表存图法这个邻接表这里面讲的很通俗&＃xff0c;想看不懂是有点难度的哦。
p是总共的点数&＃xff0c;s是总共的边数。js用于计数&＃xff0c;dis代表u,v两点的距离。a,b,c是临时储存点a到点b距离为c的临时变量。所以我会这么读入&＃xff1a;

for(int i&＃61;1;i&＃61;<s;i&＃43;&＃43;){cin>>a>>b>>c;addedge(a,b,c);
}


顺便给你一个存图的代码&＃xff1a;

void addedge(int u,int v,int dis){edge[&＃43;&＃43;js].u&＃61;u;edge[js].v&＃61;v;edge[js].dis&＃61;dis;edge[js].next&＃61;head[u];head[u]&＃61;js;return;
}


我们需要一个起始点作为源点&＃xff0c;我们就用一个变量start来储存源点吧&＃xff0c;我们在这里把点1设为源点。所以start&＃61;1。哦&＃xff0c;图还没给你们呢。
我来上一个图&＃xff1a;

我们需要一个dis数组来存源点——下面就说点1吧&＃xff0c;来储存点1到其他所有点的距离&＃xff0c;初始化的距离当然是inf,除了源点自己是0以外。在这里我使用十六进制宏定义&＃xff0c;就是定义一个很大的数&＃xff08;其实跟const是一样的&＃xff09;&＃xff0c;如图&＃xff1a;

#define inf 0x3f3f3f


0x3f3f3f就是一个16进制的很大的数&＃xff0c;等于1061109567。0x表示16进制。3f开始才是这个数字。
所以我给出的所有的输入就是酱紫&＃xff1a;

cin>>p>>s;
for(int i&＃61;1;i&＃61;<s;i&＃43;&＃43;){cin>>a>>b>>c;addedge(a,b,c);
}
memset(dis,inf,sizeof(dis)); //初始化dis数组
cin>>start;
dis[start]&＃61;0;


队列优化的话是少不了队列的。所以我们上个队列que&＃xff0c;队首begin队尾tail。
同样&＃xff0c;我们添加了一个vis数组&＃xff0c;防止已经加入队列的点重复加入。
最后&＃xff0c;我们的预处理代码&＃xff0c;预处理就是正式处理之前的定义什么的啦~就是酱紫&＃xff1a;

#include
#include
#include
using namespace std;
#define inf 0x3f3f3f
const int maxm&＃61;10001;
int p,s;
struct e{int u,v,dis,next;
}edge[maxm];
int head[maxm],js;
int a,b,c;
int que[maxm],begin,tail;
int dis[maxm],start;
int vis[maxm];


记住&＃xff0c;memset在cstring库里边。

样例模拟

图论问题最重要的是模拟&＃xff0c;我们以上图为例来模拟一次。
模拟之前我们看看我们的核心SPFA代码。

void spfa(int x){begin&＃61;end&＃61;1;que[end&＃43;&＃43;]&＃61;x;while(end-begin!&＃61;0){ //队列不为空执行循环 for(int i&＃61;head[que[begin]];i;i&＃61;edge[i].next){if(dis[edge[i].v]>dis[que[begin]]&＃43;edge[i].dis){dis[edge[i].v]&＃61;dis[que[begin]]&＃43;edge[i].dis;if(!vis[edge[i].v]){que[end&＃43;&＃43;]&＃61;edge[i].v;vis[edge[i].v]&＃61;1;}}} begin&＃43;&＃43;;}return;
}

逻辑上还是很简单的&＃xff0c;我现在给你讲讲。
初始化就是酱紫&＃xff1a;

然后我们读入的x是1&＃xff0c;队首元素就是1了。于是我从点1开始遍历&＃xff0c;发现了点2可以走&＃xff0c;所以我们就到达了这个判断&＃xff1a; i f ( d i s [ e d g e [ i ] . v ] > d i s [ q u e [ b e g i n ] ] &＃43; e d g e [ i ] . d i s ) &＃xff0c;就是当前的队首元素的dis值加上队首元素的点到当前搜到的点的权值。然后发现比dis[2]小&＃xff0c;所以执行判断内部的语句了。
换句话说&＃xff0c;就是满足了d i s [ 2] > d i s [ 1 ] 加上 点1到点2的距离。
那么我们就让 d i s [ 2] &＃61; d i s [ 1 ] 加上 点1到点2的距离 &＃xff0c;所以dis[2]就从偌大的inf变到了2&＃xff0c;再把点2入队&＃xff0c;就是执行 q u e [ e n d &＃43; &＃43; ] &＃61; e d g e [ i ] . v 这句到时候再从点2开始找有没有能进一步缩小的。同理&＃xff0c;dis[5]也从偌大的inf变成了10&＃xff0c;再把点5入队。
当然&＃xff0c;点2和点5都要在vis里面记录已经入队了。
点1只能搜到2和5&＃xff0c;那么点1的使命到此为止了&＃xff0c;我们就把点1出队&＃xff0c;就是begin&＃43;&＃43;。
所以第一轮结束的结果就是酱紫&＃xff0c;begin指向2&＃xff0c;tail指向4&＃xff1a;

当然&＃xff0c;队列不为空吧。所以继续。
只是我们从点2开始了。
点2就找到了点3&＃xff0c;进入判断i f ( d i s [ e d g e [ i ] . v ] > d i s [ q u e [ b e g i n ] ] &＃43; e d g e [ i ] . d i s ) &＃xff0c;发现比dis[3]小&＃xff0c;于是就让 d i s [ 3] &＃61; d i s [ 2 ] 加上 点2到点3的距离。然后让点3入队。当然&＃xff0c;点2还找到了点5&＃xff0c;哇&＃xff0c;又是点5&＃xff01;一样的判断&＃xff0c;我们却发现d i s [ 5] 居然大于 d i s [ 2 ] 加上 点2到点5的距离&＃xff01;没法子&＃xff0c;那么我dis[5]就要变了&＃xff01;当然是变小&＃xff01;当然&＃xff0c;入队还是一样的入队…但是点5已在队列中&＃xff0c;所以不需要再一次入队。
所以这一轮结束&＃xff0c;就是酱紫&＃xff1a;

我们从点5开始继续新一轮搜索&＃xff0c;然后搜到了点3&＃xff0c;但是d i s [ 3] 然后点3开始搜索&＃xff0c;他搜到了点4&＃xff0c;所以dis[4]&＃61;9
最后&＃xff0c;就会是酱紫的结果&＃xff0c;点4搜完后&＃xff0c;begin和tail的差就变成0了&＃xff0c;SPFA算法结束&＃xff1a;

最后我们输出dis数组&＃xff0c;就可以查看点1到所有点的最短了。
最后给出样例输出&＃xff1a;

完整代码如下&＃xff1a;

#include
#include
#include
using namespace std;
#define inf 0x3f3f3f
const int maxm&＃61;10001;
int p,s;
struct e{int u,v,dis,next;
}edge[maxm];
int head[maxm],js;
int a,b,c;
int que[maxm],begin,end;
int dis[maxm],start;
int vis[maxm];void addedge(int u,int v,int dis){edge[&＃43;&＃43;js].u&＃61;u;edge[js].v&＃61;v;edge[js].dis&＃61;dis;edge[js].next&＃61;head[u];head[u]&＃61;js;return;
}void spfa(int x){begin&＃61;end&＃61;1;que[end&＃43;&＃43;]&＃61;x;while(end-begin!&＃61;0){ //队列不为空执行循环 for(int i&＃61;head[que[begin]];i;i&＃61;edge[i].next){if(dis[edge[i].v]>dis[que[begin]]&＃43;edge[i].dis){dis[edge[i].v]&＃61;dis[que[begin]]&＃43;edge[i].dis;if(!vis[edge[i].v]){que[end&＃43;&＃43;]&＃61;edge[i].v;vis[edge[i].v]&＃61;1;}}} begin&＃43;&＃43;;}return;
}int main(){cin>>p>>s;for(int i&＃61;1;i<&＃61;s;i&＃43;&＃43;){cin>>a>>b>>c;addedge(a,b,c);}memset(dis,inf,sizeof(dis)); //初始化dis数组 cin>>start;dis[start]&＃61;0;spfa(start);for(int i&＃61;1;i<&＃61;p;i&＃43;&＃43;) cout<<dis[i]<<endl;return 0;
}