论文部分内容阅读
摘要：Bellman-ford和Spfa是解决最短路问题的基本算法，是信息学奥赛教学的基本内容。由于算法抽象性和逻辑性强，教学过程中学生对其基本原理、实现过程理解困难，导致无法灵活运用解决问题。该文旨在用具体实例结合图表对算法执行过程进行详细解析，深刻剖析了算法的优化原理，有效解决了学生理解和应用困难的问题。
关键词：Bellman-ford;Spfa;算法解析
中图分类号：TP312 文献标识码：A
文章编号：1009-3044（2021）30-0079-03
开放科学（资源服务）標识码（OSID）：
1 前言
Bellman-Ford算法由查理德·贝尔曼和莱斯特·福特创立的，其基本思想是利用松弛原理反复对边集中的每条边进行松弛迭代操作，同时更新顶点集合中每个顶点的最短路径值并记录其最短路径上的前驱结点，达到收敛时停止迭代操作[1]。由于反复对边集中的每条边进行松弛，因此产生了很多冗余的松弛操作，造成时间复杂度较高。Spfa算法针对这一问题进行了优化，其核心思想是用FIFO队列保存已经被松弛过的顶点，只处理入队的顶点，并且不断迭代以求得最短路径。因此，深刻理解Bellman-Ford算法有助于充分理解和应用Spfa算法解决实际问题[2]。下面我们用具体实例来展开探讨这两个算法的实现过程。
例题：如图1所示，求1号顶点到其余各顶点的最短距离。
我们用d 数组记录起点到其余各点的最短路径值，用s、e、t三个数组来存储边的信息。例如第i条边存储在s[i]、e[i]、t[i]中，表示从顶点s[i]到e[i]这条边的权值为t[i]。
给出边的顺序如下表：
2 Bellman-Ford算法题解
用d数组来存储1号顶点到其余各点的路径值。
初始化如下表：
根据边给出的顺序，先处理第一条边“2-4-3”即判断一下d[4]是否大于d[2]+3，由于此时d[4]和d[2]都是无穷大，因此这条边松弛失败。接下来处理第二条边“1-2-（-1）”， 我们发现d[2] > d[1] + （-1） ，通过这条边可以使d[2]的值从∞变为 -1 ，所以这个点松弛成功。我们可以用同样的方法来处理第三条边到第七条边，对所有的边进行一遍松弛操作后的结果如下：
第一轮对所有边进行松弛以后，结果如下表所示：
第二轮对所有边进行松弛以后，结果如下表所示：
在这轮松弛中，通过“2 4 3”（2→4）这条边，更新了1号顶点到4号顶点的距离（d[4]） 。这条边在第一轮松弛失败，却在第二轮松弛成功。原因是在第一 轮松弛过后，1号顶点到2号顶点的距离（d[2]） 已经发生了变化，这一轮再通过“2 4 3”（2-→4）这条边进行松弛的时候，可以使1号顶点到4号顶点的距离（d[4]） 的值变小。也就是说，第一轮遍历图中所有边进行松弛操作之后，得到的是起点“经过一条边”到达其余各点的最短路径值。第二轮遍历图中所有边进行松弛操作之后，得到的是从起点“至多经过两条边”到达其余各点的最短路径值。如果进行n-1轮的话，得到的就是起点“至多经过n-1条边”到达其余各顶点的最短路径值。在一个含有n个顶点的图中，由于任意两点之间的最短路径最多经过n-1条边，因此最多松弛n-1轮。
第三轮对所有边进行松弛以后，结果如下表所示：
第四轮对所有边松弛以后，结果如下表所示：
从第三轮开始，对所有边进行松弛操作，发现没有顶点需要更新，此时便可以提前结束遍历，优化效率。最后表中数据就是1号顶点到其余各点的最短路径值。
根据以上分析本题完整代码如下：
#include<bits/stdc++.h>
const int maxd = 1e9;
using namespace std;
int main（）{
int s[100] ， e[100] ， t[100] ， d[100] ， n ， m ;
cin>>n>>m;
for（int i = 1 ; i <= m ; i ++）
cin>>s[i] >>e[i] >>t[i];
for（int i = 1 ; i <= n ; i ++）d[i] = maxd;
d[1] = 0;
while（1）{
bool upd=false;
for（int j = 1 ; j <= m ; j ++）{
if（d[e[j]] > d[s[j]] + t[j]）{
d[e[j]] = d[s[j]] + t[j];
upd=true;
}
}
if（upd==false） break;
}
for（int i = 1 ; i <= n ; i ++） cout<<d[i]<<"";
return 0 ;
}
/*
5 7
2 4 3
1 2 -1
1 3 5
5 3 4
2 3 -2
2 5 6
4 5 2
*/ 3 Spfa算法题解
Spfa是Bellman-Ford算法的一种队列实现，为了减少了不必要的冗余计算，我们用一个队列来维护。初始时将起始点加入队列，每次从队列中取出队首元素，并对所有与他相邻的点进行松弛，并将松弛成功的顶点入队，直到队列为空时算法结束。
针对本例题的具体实现过程如下：
首先建立起始点1到其余各点的最短路径表格，d[i]表示起点1到i点的最短路径值。
首先源点1入队，当队列非空时：
队首元素1出队，对以1为起点的所有边的终点（2、3）进行松弛操作，此时路径表格状态为：
松弛以后，2和3两个顶点的最短路径估值变小，而这两个点队列中都没有，因此入队。
队首元素2出队，对以2为起点的所有边的终点（3，4，5）依次进行松弛操作，此时路径表格状态为：
此时，3，4，5三个顶点的最短路径估值变小，其中3这个点已经在队列中，不用入队，4，5两个点入队。
队首元素3出队，但是以3为起点没有出边，因此此时无松弛操作。
队首元素4出队，对以4为起点的所有边的终点（5）进行松弛，此时路径表格状态为：
队首元素5出队，但是以5为起点没有出边，此时无松弛操作，并且队列已空，算法结束，表中数据便是顶点1到其余各点的最短路径值。
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int cnt，head[N]，d[N]，n，m，vis[N];
struct edge{
int v，nxt，w;
}a[N*2];
void addedge（int u，int v，int w）{
a[++cnt].v=v;
a[cnt].w=w;
a[cnt].nxt=head[u];
head[u]=cnt;
}
void spfa（int s）{
queue<int>q;
memset（d，0x3f，sizeof（d））;
d[s]=0;
q.push（s）;
vis[s]=1;
while（！q.empty（））{
int now=q.front（）;
q.pop（）;
vis[now]=0;
for（int i=head[now];i;i=a[i].nxt）{
int to=a[i].v;
if（a[i].w+d[now]<=d[to]）{
d[to]=a[i].w+d[now];
if（！vis[to]）{
q.push（to）;
vis[to]=1;
}
}
}
}
}
int main（）{
cin>>n>>m;
for（int i=1;i<=m;i++）{
int x，y，w;
cin>>x>>y>>w;
addedge（x，y，w）;
}
spfa（1）;
for（int i=1;i<=n;i++）cout<<d[i]<<"";
return 0;
}
/*
5 7
2 4 3
1 2 -1
1 3 5
5 3 4
2 3 -2
2 5 6
4 5 2
*/
4兩种算法的联系和区别
Bellman-Ford 算法时间复杂度为 O （nm），最多需要执行 n-1 次循环，如果执行了n次循环，说明图中含有负圈[3]。Spfa算法是为了改进Bellman-Ford算法的效率而提出来的，在最优的情况下，每个节点只入队一次，这时退化为广度优先搜索，在最坏情况下，每个节点都入队 n-1 次，此时 Spfa 算法退化为 Bellman-Ford 算法，时间复杂度为 O（nm）。如果某个节点的入队次数超过 n 次，说明图中肯定含有负圈[4-5]。
由于这两种算法均采用邻接表的方式存储边的信息，因此他们的空间复杂度均为 O（m）。
它们都可以解决负权图问题，并能够判断图中是否含有负圈，都适用于稀疏图。
由以上分析可以看出，Bellman-Ford算法可解决的问题Spfa算法也都适用。因此，奥赛解题中更常用Spfa算法。但是，Bellman-Ford算法思想精妙，是Spfa算法的前置知识，在学习中先理解Bellman-Ford算法更有利于对Spfa算法的理解和应用。
参考文献：
[1] 陈雨婕.用图示法解析最短路径算法[J].电脑知识与技术，2007，3（24）：54-56.
[2] 刘磊，王燕燕，申春，等.Bellman-Ford算法性能可移植的GPU并行优化[J].吉林大学学报（工学版），2015，45（5）：1559-1564.
[3] 韩伟一.固定序Bellman-Ford算法的一个改进[J].哈尔滨工业大学学报，2014，46（11）：58-62，69.
[4] 段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报，1994，29（2）：207-212.
[5] 夏正冬，卜天明，张居阳.SPFA算法的分析及改进[J].计算机科学，2014，41（6）：180-184，213.
【通联编辑：唐一东】
关键词：Bellman-ford;Spfa;算法解析
中图分类号：TP312 文献标识码：A
文章编号：1009-3044（2021）30-0079-03
开放科学（资源服务）標识码（OSID）：
1 前言
Bellman-Ford算法由查理德·贝尔曼和莱斯特·福特创立的，其基本思想是利用松弛原理反复对边集中的每条边进行松弛迭代操作，同时更新顶点集合中每个顶点的最短路径值并记录其最短路径上的前驱结点，达到收敛时停止迭代操作[1]。由于反复对边集中的每条边进行松弛，因此产生了很多冗余的松弛操作，造成时间复杂度较高。Spfa算法针对这一问题进行了优化，其核心思想是用FIFO队列保存已经被松弛过的顶点，只处理入队的顶点，并且不断迭代以求得最短路径。因此，深刻理解Bellman-Ford算法有助于充分理解和应用Spfa算法解决实际问题[2]。下面我们用具体实例来展开探讨这两个算法的实现过程。
例题：如图1所示，求1号顶点到其余各顶点的最短距离。
我们用d 数组记录起点到其余各点的最短路径值，用s、e、t三个数组来存储边的信息。例如第i条边存储在s[i]、e[i]、t[i]中，表示从顶点s[i]到e[i]这条边的权值为t[i]。
给出边的顺序如下表：
2 Bellman-Ford算法题解
用d数组来存储1号顶点到其余各点的路径值。
初始化如下表：
根据边给出的顺序，先处理第一条边“2-4-3”即判断一下d[4]是否大于d[2]+3，由于此时d[4]和d[2]都是无穷大，因此这条边松弛失败。接下来处理第二条边“1-2-（-1）”， 我们发现d[2] > d[1] + （-1） ，通过这条边可以使d[2]的值从∞变为 -1 ，所以这个点松弛成功。我们可以用同样的方法来处理第三条边到第七条边，对所有的边进行一遍松弛操作后的结果如下：
第一轮对所有边进行松弛以后，结果如下表所示：
第二轮对所有边进行松弛以后，结果如下表所示：
在这轮松弛中，通过“2 4 3”（2→4）这条边，更新了1号顶点到4号顶点的距离（d[4]） 。这条边在第一轮松弛失败，却在第二轮松弛成功。原因是在第一 轮松弛过后，1号顶点到2号顶点的距离（d[2]） 已经发生了变化，这一轮再通过“2 4 3”（2-→4）这条边进行松弛的时候，可以使1号顶点到4号顶点的距离（d[4]） 的值变小。也就是说，第一轮遍历图中所有边进行松弛操作之后，得到的是起点“经过一条边”到达其余各点的最短路径值。第二轮遍历图中所有边进行松弛操作之后，得到的是从起点“至多经过两条边”到达其余各点的最短路径值。如果进行n-1轮的话，得到的就是起点“至多经过n-1条边”到达其余各顶点的最短路径值。在一个含有n个顶点的图中，由于任意两点之间的最短路径最多经过n-1条边，因此最多松弛n-1轮。
第三轮对所有边进行松弛以后，结果如下表所示：
第四轮对所有边松弛以后，结果如下表所示：
从第三轮开始，对所有边进行松弛操作，发现没有顶点需要更新，此时便可以提前结束遍历，优化效率。最后表中数据就是1号顶点到其余各点的最短路径值。
根据以上分析本题完整代码如下：
#include<bits/stdc++.h>
const int maxd = 1e9;
using namespace std;
int main（）{
int s[100] ， e[100] ， t[100] ， d[100] ， n ， m ;
cin>>n>>m;
for（int i = 1 ; i <= m ; i ++）
cin>>s[i] >>e[i] >>t[i];
for（int i = 1 ; i <= n ; i ++）d[i] = maxd;
d[1] = 0;
while（1）{
bool upd=false;
for（int j = 1 ; j <= m ; j ++）{
if（d[e[j]] > d[s[j]] + t[j]）{
d[e[j]] = d[s[j]] + t[j];
upd=true;
}
}
if（upd==false） break;
}
for（int i = 1 ; i <= n ; i ++） cout<<d[i]<<"";
return 0 ;
}
/*
5 7
2 4 3
1 2 -1
1 3 5
5 3 4
2 3 -2
2 5 6
4 5 2
*/ 3 Spfa算法题解
Spfa是Bellman-Ford算法的一种队列实现，为了减少了不必要的冗余计算，我们用一个队列来维护。初始时将起始点加入队列，每次从队列中取出队首元素，并对所有与他相邻的点进行松弛，并将松弛成功的顶点入队，直到队列为空时算法结束。
针对本例题的具体实现过程如下：
首先建立起始点1到其余各点的最短路径表格，d[i]表示起点1到i点的最短路径值。
首先源点1入队，当队列非空时：
队首元素1出队，对以1为起点的所有边的终点（2、3）进行松弛操作，此时路径表格状态为：
松弛以后，2和3两个顶点的最短路径估值变小，而这两个点队列中都没有，因此入队。
队首元素2出队，对以2为起点的所有边的终点（3，4，5）依次进行松弛操作，此时路径表格状态为：
此时，3，4，5三个顶点的最短路径估值变小，其中3这个点已经在队列中，不用入队，4，5两个点入队。
队首元素3出队，但是以3为起点没有出边，因此此时无松弛操作。
队首元素4出队，对以4为起点的所有边的终点（5）进行松弛，此时路径表格状态为：
队首元素5出队，但是以5为起点没有出边，此时无松弛操作，并且队列已空，算法结束，表中数据便是顶点1到其余各点的最短路径值。
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int cnt，head[N]，d[N]，n，m，vis[N];
struct edge{
int v，nxt，w;
}a[N*2];
void addedge（int u，int v，int w）{
a[++cnt].v=v;
a[cnt].w=w;
a[cnt].nxt=head[u];
head[u]=cnt;
}
void spfa（int s）{
queue<int>q;
memset（d，0x3f，sizeof（d））;
d[s]=0;
q.push（s）;
vis[s]=1;
while（！q.empty（））{
int now=q.front（）;
q.pop（）;
vis[now]=0;
for（int i=head[now];i;i=a[i].nxt）{
int to=a[i].v;
if（a[i].w+d[now]<=d[to]）{
d[to]=a[i].w+d[now];
if（！vis[to]）{
q.push（to）;
vis[to]=1;
}
}
}
}
}
int main（）{
cin>>n>>m;
for（int i=1;i<=m;i++）{
int x，y，w;
cin>>x>>y>>w;
addedge（x，y，w）;
}
spfa（1）;
for（int i=1;i<=n;i++）cout<<d[i]<<"";
return 0;
}
/*
5 7
2 4 3
1 2 -1
1 3 5
5 3 4
2 3 -2
2 5 6
4 5 2
*/
4兩种算法的联系和区别
Bellman-Ford 算法时间复杂度为 O （nm），最多需要执行 n-1 次循环，如果执行了n次循环，说明图中含有负圈[3]。Spfa算法是为了改进Bellman-Ford算法的效率而提出来的，在最优的情况下，每个节点只入队一次，这时退化为广度优先搜索，在最坏情况下，每个节点都入队 n-1 次，此时 Spfa 算法退化为 Bellman-Ford 算法，时间复杂度为 O（nm）。如果某个节点的入队次数超过 n 次，说明图中肯定含有负圈[4-5]。
由于这两种算法均采用邻接表的方式存储边的信息，因此他们的空间复杂度均为 O（m）。
它们都可以解决负权图问题，并能够判断图中是否含有负圈，都适用于稀疏图。
由以上分析可以看出，Bellman-Ford算法可解决的问题Spfa算法也都适用。因此，奥赛解题中更常用Spfa算法。但是，Bellman-Ford算法思想精妙，是Spfa算法的前置知识，在学习中先理解Bellman-Ford算法更有利于对Spfa算法的理解和应用。
参考文献：
[1] 陈雨婕.用图示法解析最短路径算法[J].电脑知识与技术，2007，3（24）：54-56.
[2] 刘磊，王燕燕，申春，等.Bellman-Ford算法性能可移植的GPU并行优化[J].吉林大学学报（工学版），2015，45（5）：1559-1564.
[3] 韩伟一.固定序Bellman-Ford算法的一个改进[J].哈尔滨工业大学学报，2014，46（11）：58-62，69.
[4] 段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报，1994，29（2）：207-212.
[5] 夏正冬，卜天明，张居阳.SPFA算法的分析及改进[J].计算机科学，2014，41（6）：180-184，213.
【通联编辑：唐一东】