#创作计划#贝尔曼-福特算法精讲
2025-12-20 07:37:07
发布于：浙江
别催了开始写啦
←第一篇
----------------------------------------------------第二篇----------------------------------------------------------
前言：
本文适合深色模式观看
本篇衔接第一篇《迪杰斯特拉算法精讲》
这是第二篇帖子，再不写老师就要拧我头了。
正文：
第一部分：算法讲解。
来源：百度百科
贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的，求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。
。
还记得上文的迪杰斯特拉算法吗？迪杰斯特拉算法是，而贝尔曼福特算法是。贝尔曼福特算法基于动态规划的思想，对图进行松弛操作。他的算法实现是：拿出所有的边，更新这个边所到达的点的最短路径。一般呢要进行 [1] 次松弛操作。但是，当你进行了一轮操作后没有任何一个点被更新，那么你就可以直接结束遍历。因为你已经找到了图的最短路径。时间复杂度为 [1:1]。事实上下一章我们会讲到它的优化算法 。但是 容易被构造数据卡，所以说某些时候还是用贝尔曼福特好点。（详见ppl的评论）
那么还是和上一篇一样，画一个图来模拟贝尔曼福特算法的实现。由于贝尔曼福特算法的实现方式，所以我画一个小一点的图。
我们定义 数组为图中点的最短路径， 结构体数组为该图的所有边。这里采用 [2] 的形式表示，变量 代表该轮是否更新（初始为 ）。下边的箭头则代表当前遍历的点。这里已经初始化好了（可以参考迪杰斯特拉算法讲解）。
先进行第一轮遍历。按照 结构体开始遍历。 到 。计算出可得最短路径（当前，后边不再提示）为 ，小于无穷，更新 数组：
现在遍历第二条边， 到 。更新 点最短路径为 。
遍历第三条边， 到 。 ，不做更新：
为了节省时间，现在直接把第一轮遍历完：
那么根据贝尔曼福特算法，我们还需进行 次遍历。现在进行第二次遍历：
那么第二轮遍历结束，我们发现没有任何一个节点更新。所以贝尔曼福特算法结束。
代码解析：
首先我们需要一个结构体数组来储存每一条边
struct node{
int from,to,len;//出发点，要去的点，长度
}a[10010];
之后，我们先初始化数组，并储存图的相关数据
for(int i=1;i<=n;i++){
dis[i] = 1e9; //初始化数组
}dis[s]=0;//起点
for(int i=1;i<=m;i++){
cin >> a[i].from >> a[i].to >> a[i].len;//输入图的相关数据
}
接下来是核心代码：
首先取出当前的边，分别为当前点，要去的点以及长度。
之后，我们判断走到这个点的最短路径是否可以更新，如果可以则更新；不可以( p==false )就不更新，直接break
for(int k=1;k<n;k++){
bool p=false;
for(int i=1;i<=m;i++){
from=a[i].from,to=a[i].to,len=a[i].len;//赋值。
if(dis[to]>dis[from]+len){
p=true;
dis[to]=dis[from]+len;
}
//判断走到to这个点能否更新最短距离
}if(p==false)break;
}
最后输出即可。
完整代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int from,to,len;//出发点，要去的点，长度
}a[10010];
int n,m,s,t;//依托不知名的东西,分别是节点数，边数，起点，终点
int dis[10010];
signed main(){
cin >> n >> m >> s >> t;
for(int i=1;i<=n;i++){
dis[i]=1e9; //初始化数组
}
dis[s]=0;//起点
for(int i=1;i<=m;i++){
cin >> a[i].from >> a[i].to >> a[i].len;//输入图的相关数据
}
int from,to,len;//出发点，要去的点，长度
for(int k=1;k<n;k++){
bool p=false;
for(int i=1;i<=m;i++){
from=a[i].from,to=a[i].to,len=a[i].len;//赋值。
if(dis[to]>dis[from]+len){
p=true;
dis[to]=dis[from]+len;
}
//判断走到to这个点能否更新最短距离
}if(p==false)break;
}
cout << dis[t];
//输出走到t的最短路径
return 0;
}
SPFA：
注意到，只有当一个节点更新后，（这个节点）后边的所有节点才会更新。所以我们可以用队列储存节点，把更新过的节点加入队列中。当从队列取出来之后，更新其所有的后继结点（在此过程中有更新的节点也要入队）。并将该节点标记为出队。这里就不细讲了。直接贴代码。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int dis[10010],vis[10010],mp[5010][5010];
signed main(){
cin >> n >> m >> s >>t;
for(int i=1;i<=n;i++){
dis[i]=1e9; //初始化数组
}for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
mp[i][j]=1e9;//初始化*2
}
}for(int i=1;i<=m;i++){
int s,t,v;
cin >> s >> t >> v;
mp[s][t]=v;//输入图并储存
}dis[s]=0;
vis[s]=1;
queue<int> a;
a.push(s);
while(a.size()){
int u=a.front();//取出队首
a.pop();//取出
vis[u]=0;//将该点标记为不在队列中
for(int i=1;i<=n;i++){
if(dis[i]>dis[u]+mp[u][i]){
dis[i]=dis[u]+mp[u][i];//更新，进行松弛操作
if(!vis[i]){//如果该点被更改
vis[i]=1; //标记
a.push(i);//入队
}
}
}
}
cout << dis[t];
return 0;
}
但是， SPFA 算法容易被卡时间复杂度使其退化到 的复杂度。所以在实际竞赛中，谨慎使用 SPFA。
注解：
全部评论 9
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
2025-12-20 来自 浙江
1ddd,小女子提供一下SPFAの模板
#include<bits/stdc++.h> using namespace std; int n,m,s,t; int d[15555]; int vis[15555]={0}; int a[2005][2005]; int main(){ scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=n;i++){ d[i]=1e9; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=1e9; } } int x,y,z; for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); a[x][y]=z; }//二维数组邻接矩阵 d[s]=0;//起点赋值为0 vis[s]=1;//起点打标记 queue<int> q; q.push(s);//起点入队 while(!q.empty()){ int u=q.front();//取队尾元素 q.pop();//删除 vis[u]=0;//标记 for(int i=1;i<=n;i++){ if(d[i]>d[u]+a[u][i]){ //松弛:要去的点>当前的起点+这段路程 d[i]=d[u]+a[u][i]; if(!vis[i]){//有无重复入队 vis[i]=1; q.push(i); } } } } printf("%d",d[t]); return 0; }2025-10-24 来自 浙江
0
有帮助，赞一个