图论——Bellman-Ford算法


这篇里,我们讲到,对于有负权值的情况下,一般用Bellman_Ford。

今天就来详述一下Bellman_Ford与其例题。

Bellman_Ford的思想非常简单,首先第一层枚举点,第二层枚举每一条边。

与其说第一层是枚举,其实不如说它是单纯循环,因为,有些题目中,第一层就是单纯循环,对于需要枚举节点的题目来说,它还是一样的写法。

第二层循环有3个变量:a,b,w,a表示边的起点,b表示边的终点,w表示边的权值,Bellman_Ford的存边方式很灵活,只要保证能遍历到每条边的起点、终点、权值就可以了,不一定非得用邻接表或邻接矩阵。我们可以开一个结构体,里面放3个变量:a,b,w;一个结构体数组edge[]既然都用了edge,所以这就是存边用的。

而它循环内执行的操作和Dijkstra十分相像。dis[edge[j].b]=min(dis[edge[j].b],bc[edge[j].a]+edge[j].w);就可以。再看一个例题:

  求出从1号点到n号点的最多经过k条边的最短距离,如果无法从1号点走到n号点,输出impossible

这道题只能用Bellman_Ford做,其他均不可以(包括SPFA),在这一题中,第一层循环中,我们枚举的就是k因为只要枚举次数小于k次,就1一定能保证经过的边数小于k。

最后再判断,如果求出的答案是初始值,那么输出不可能就行。

代码: 

#include<bits/stdc++.h>
using namespace std;
int n,m,dis[505],bc[505],aa,bb,ww,k;
struct aaa{
    int a,b,w;
}edge[10005];
int main(){
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>aa>>bb>>ww;
        edge[i]={aa,bb,ww};
    }
    for(int i=1;i<=k;i++){
        memcpy(bc,dis,sizeof dis);
        for(int j=1;j<=m;j++)                         
            dis[edge[j].b]=min(dis[edge[j].b],bc[edge[j].a]+edge[j].w);
    }
    if(dis[n]>0x3f3f3f3f/2) cout<<"impossible";
    else cout<<dis[n];
    return 0;
} 

  

原创文章,作者:wure,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/275194.html

(0)
上一篇 2022年7月18日 17:12
下一篇 2022年7月18日 17:12

相关推荐

发表回复

登录后才能评论