历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 853. Bellman_ford算法原题链接简单

作者：

orzorz , 2020-02-27 16:11:44 , 所有人可见 , 阅读 7251

52

36

bellman_ford算法

1)初始化所有点到源点的距离为∞,把源点到自己的距离设置为0；
2)不管3721遍历n次;每次遍历m条边，用每一条边去更新各点到源点的距离。

值得注意的是

1) 需要把dist数组进行一个备份，这样防止每次更新的时候出现串联；
2) 由于存在负权边，因此return -1的条件就要改成dist[n]>0x3f3f3f3f/2;
3) 上面所谓的n次遍历的实际含义是当前的最短路径最多有n-1条边，这也就解释了为啥要i遍历到n的时候退出循环了，因为只有n个点,最短路径无环最多就存在n-1条边。
4) 这里无需对重边和自环做单独的处理：
1] 重边：由于遍历了所有的边，总会遍历到较短的那一条; 2] 自环: 有自环就有自环啊，反正又不会死循环;
5) 令人愉悦的是，该算法无非就是循环n次然后遍历所有的边，因此不需要做什么特别的存储，只要把所有的边的信息存下来能够遍历就行;
6）bellman_ford算法可以存在负权回路，因为它求得的最短路是有限制的，是限制了边数的，这样不会永久的走下去，会得到一个解；
7)SPFA算法各方面优于该算法，但是在碰到限制了最短路径上边的长度时就只能用bellman_ford了，此时直接把n重循环改成k次循环即可

代码

#include<iostream>
#include<cstring>
using namespace std;

const int N=510,M=10010;

struct Edge{
    int a;
    int b;
    int w;
}e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组放置串联
int n,m,k;//k代表最短路径最多包涵k条边

int bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++){//k次循环
        memcpy(back,dist,sizeof dist);
        for(int j=0;j<m;j++){//遍历所有边
            int a=e[j].a,b=e[j].b,w=e[j].w;
            dist[b]=min(dist[b],back[a]+w);//使用backup:避免给a更新后立马更新b,这样b一次性最短路径就多了两条边出来
        }

    }
    if(dist[n]>0x3f3f3f3f/2) return -1;
    else return dist[n];

}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        e[i]={a,b,w};
    }
    int res=bellman_ford();
    if(res==-1) puts("impossible");
    else cout<<res;


    return 0;
}

19 评论

彼岸花开_2 2022-09-08 16:13

加强的那一个数据怎么才能过

cai_xing 2023-08-05 19:53

y总代码已经更新了

ak44711 9个月前

就一个数据，dist[n]==-1的时候，直接在函数里面输出，靠返回值返回的话会出问题

qianyixin 22天前

if (dist[n] > 0x3f3f3f3f / 2) return -1;
这里为什么是判断dist[n]>0x3f3f3f3f/2啊

lagrangist 2022-08-21 14:02

#include<iostream>
#include<cstring>

using namespace std;

const int N = 510, M = 10010;

struct Edge {
    int a;
    int b;
    int w;
} e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {//k次循环
        memcpy(back, dist, sizeof dist);
        for (int j = 0; j < m; j++) {//遍历所有边
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dist[b] = min(dist[b], back[a] + w);
            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    else return dist[n];

}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        e[i] = {a, b, w};
    }
    int res = bellman_ford();
    if (res == -1) puts("impossible");
    else cout << res;

    return 0;
}

作者：松鼠爱葡萄
链接：#include<iostream>
#include<cstring>

using namespace std;

const int N = 510, M = 10010;

struct Edge {
    int a;
    int b;
    int w;
} e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {//k次循环
        memcpy(back, dist, sizeof dist);
        for (int j = 0; j < m; j++) {//遍历所有边
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dist[b] = min(dist[b], back[a] + w);
            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    else return dist[n];

}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        e[i] = {a, b, w};
    }
    int res = bellman_ford();
    if (res == -1) puts("impossible");
    else cout << res;

    return 0;
}

作者：松鼠爱葡萄
链接：https://www.acwing.com/solution/content/14088/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。