#创作计划#贝尔曼-福特算法精讲

userId_undefined
༺དༀ༒∞░∞༒ༀཌ༻（不加团）
7月全勤卷王8月全勤卷王题解仙人GESP4级传道者BUG超度大师

2025-12-20 07:37:07

发布于：浙江

125阅读
0回复
0点赞

别催了开始写啦

←第一篇

----------------------------------------------------第二篇----------------------------------------------------------

前言：

本文适合深色模式观看

本篇衔接第一篇《迪杰斯特拉算法精讲》
这是第二篇帖子，再不写老师就要拧我头了。

正文：

第一部分：算法讲解。

来源：百度百科

贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的，求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。
你可能不认识贝尔曼，但你一定学过他与其他人发明的\color{red}你可能不认识贝尔曼，但你一定学过他与其他人发明的 动态规划\huge{\color{red}动态规划}。
还记得上文的迪杰斯特拉算法吗？迪杰斯特拉算法是选边\color{red}选边，而贝尔曼福特算法是选点\color{red}选点。贝尔曼福特算法基于动态规划的思想，对图进行松弛操作。他的算法实现是：拿出所有的边，更新这个边所到达的点的最短路径。一般呢要进行 n−1n-1 [1] 次松弛操作。但是，当你进行了一轮操作后没有任何一个点被更新，那么你就可以直接结束遍历。因为你已经找到了图的最短路径。时间复杂度为 O(nm)O(nm)[1:1]。事实上下一章我们会讲到它的优化算法 SPFASPFA 。但是 SPFASPFA 容易被构造数据卡，所以说某些时候还是用贝尔曼福特好点。（详见ppl的评论）

那么还是和上一篇一样，画一个图来模拟贝尔曼福特算法的实现。由于贝尔曼福特算法的实现方式，所以我画一个小一点的图。


我们定义 disdis 数组为图中点的最短路径，nodenode 结构体数组为该图的所有边。这里采用 (from,len,to)(from,len,to)[2] 的形式表示，变量 pp 代表该轮是否更新（初始为 falsefalse）。下边的箭头则代表当前遍历的点。这里已经初始化好了（可以参考迪杰斯特拉算法讲解）。

先进行第一轮遍历。按照 nodenode 结构体开始遍历。AA 到 DD。计算出可得最短路径（当前，后边不再提示）为 22 ，小于无穷，更新 disdis 数组：

现在遍历第二条边，AA 到 BB。更新 BB 点最短路径为 −2-2。

遍历第三条边，DD 到 BB。 2+3<−22+3 < -2 ，不做更新：
为了节省时间，现在直接把第一轮遍历完：

那么根据贝尔曼福特算法，我们还需进行 n−2n-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 算法容易被卡时间复杂度使其退化到 O(nm)O(nm) 的复杂度。所以在实际竞赛中，谨慎使用 SPFA。

注解：

  1. 这里设 nn 为这个图的边数, mm 为这个图的节点数。 ↩︎ ↩︎

  2. fromfrom , lenlen 和 toto 指从哪个点来，到哪个点去，两点之间边的权值是多少（英文看得懂吧） ↩︎

userId_undefined
去预览
0/2000

全部评论 9

热门讨论