# Bellman-ford

用途:

  1. 判负环
  2. 计算含有负权边的最短路径

重边不会影响答案,因为 Bellman-ford 会遍历所有的边

# 算法流程

先存边,Bellman-ford 的存边十分随意,什么储存方式都可以,只有一个要求,就是每次都要遍历到所有的边!

既然如此就用一个结构体去存,一个 for 循环就可以遍历到所有的边了。

struct node{
	int u,v,w
}e[MAXN];

算法十分简单,每次只要让所有的边进行一次更新即可,如果不存在负环,那么一个点最多被 n-1 个点更新 (除了自己),所以外层循环遍历 n-1 次,内层循环遍历每一条边

for(int i=1;i<n;i++){
	for(int j=1;j<=m;j++){
        int u=e[j].u,v=e[j].v,w=e[j].w;
		dis[v]=min(dis[v],dis[u]+w);
	}
}

如果存在负环,那么经过上面的松弛操作后,一定还有点还可以被松弛,负环可以把环上点能到的所有点的权值都松弛到无限小,遍历所有点,检查是否还有点可以被松弛,如果有,则存在负环,否则不存在。

for(i=1;i<=n;i++){
    if(dis[e[i].v]>dis[e[i].u]+e[i].w){
        return 0;
    }
}

# 输出路径

用 pre 数组保存该节点由谁更新的,初始化时把所有的 pre 初始化为起点,最后从终点开始往回走,直到走到起点,输出路径。

更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝