#创作计划#贝尔曼-福特算法精讲
2025-11-21 12:00:37
发布于：浙江
别催了开始写啦
←第一篇
----------------------------------------------------第二篇----------------------------------------------------------
前言：
本文适合深色模式观看
本篇衔接第一篇《迪杰斯特拉算法精讲》
这是第二篇帖子，再不写老师就要拧我头了。
这次依旧有头图
被鲁迅医治精神的忘穿秋裤（详见鲁迅的《从百草园到三味书屋》）
正文：
第一部分：算法讲解。
来源：百度百科
贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的，求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。
。
还记得上文的迪杰斯特拉算法吗？迪杰斯特拉算法是，而贝尔曼福特算法是。贝尔曼福特算法基于动态规划的思想，对图进行松弛操作。他的算法实现是：拿出所有的边，更新这个边所到达的点的最短路径。一般呢要进行 [1] 次松弛操作。但是，当你进行了一轮操作后没有任何一个点被更新，那么你就可以直接结束遍历。因为你已经找到了图的最短路径。时间复杂度为 [1:1]。事实上下一章我们会讲到它的优化算法 。但是 容易被构造数据卡，所以说某些时候还是用贝尔曼福特好点。（详见ppl的评论）
那么还是和上一篇一样，画一个图来模拟贝尔曼福特算法的实现。由于贝尔曼福特算法的实现方式，所以我画一个小一点的图。
我们定义 数组为图中点的最短路径， 结构体数组为该图的所有边。这里采用 [2] 的形式表示，变量 代表该轮是否更新（初始为 ）。下边的箭头则代表当前遍历的点。这里已经初始化好了（可以参考迪杰斯特拉算法讲解）。
先进行第一轮遍历。按照 结构体开始遍历。 到 。计算出可得最短路径（当前，后边不再提示）为 ，小于无穷，更新 数组：
现在遍历第二条边， 到 。更新 点最短路径为 。
遍历第三条边， 到 。 ，不做更新：
为了节省时间，现在直接把第一轮遍历完：
那么根据贝尔曼福特算法，我们还需进行 次遍历。现在进行第二次遍历：
那么第二轮遍历结束，我们发现没有任何一个节点更新。所以贝尔曼福特算法结束。
代码解析：
首先我们需要一个结构体数组来储存每一条边
struct node{
int from,to,len;//出发点，要去的点，长度
}a[10010];
之后，我们先初始化数组，
注解：
全部评论 7
ddd,小女子提供一下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
有帮助，赞一个