Bellman–Ford算法模板
2026-01-31 11:49:35
发布于：四川
1阅读
0回复
0点赞
//Bellman–Ford算法模板
//Bellman-Ford算法：求解单源最短路径，并检测起点s是否可达负权环
//洛谷 P3385
//核心思想:若非负环最多跑 n-1 次
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn=1e6+5;
int head[maxn],node;
struct Edge{
int v,w,pre;
}edge[maxn];
inline void add_edge(int u,int v,int w){
edge[++node].v=v;
edge[node].w=w;
edge[node].pre=head[u];
head[u]=node;
}
int dis[maxn];
bool vis[maxn];
int n,m;
//s为最短路径的起点
//返回值：true表示从s出发能到达负权环 false表示无负权环(或负权环不可达)
//全局依赖：
//dis[]:存储起点s到各节点的最短路径长度 inf表示不可达的无穷大
//n:图的总节点数 head[]/edge[]链式前向星存储有向图(edge[i].v=终点 edge[i].w=边权)
bool bellmanford(int s){
//初始化最短距离数组 最初距离都初始化为inf
memset(dis,inf,sizeof dis);
dis[s]=0;//初始化起点 (起点到自身的距离为0)
bool flag;//记录每一轮松弛操作中是否发生了路径更新(是否松弛)
//Bellman-Ford核心循环:最多执行n轮(n为节点数)
//原理:无负环时,最短路径的边数最多为n-1(否则必存在环) n-1轮松弛即可确定所有最短路径
for(int k=1;k<=n;++k){
flag=0;//重置标记,默认无松弛操作
//便利所有节点u 通过u的出边松弛其邻接节点v
for(int u=1;u<=n;++u){
//剪枝优化：若u到s的最短路径为无穷大,则u的出边无法松弛任何节点
if(dis[u]==inf){
continue;//跳过不可达节点
}
//遍历u的所有出边(链式前向星遍历)
for(int i=head[u];i;i=edge[i].pre){
int v=edge[i].v;
//松弛操作:若经u到v的路径比v当前的最短路径更短,则更新
if(dis[v]>dis[u]+edge[i].w){
dis[v]=dis[u]+edge[i].w;//更新v的最短路
flag=true;//标记本轮进行了松弛操作
}
}
}
//提前终止：若本轮无任何松弛操作，说明所有最短路径已确定，无需继续循环
if(!flag){
break;
}
}
//负环检测：若第n轮循环仍能松弛 则存在从s可达的负权环
//原理：无负环时,n-1轮松弛后所有最短路径已确定，第n轮不可能再松弛；
//若第n轮仍能松弛,说明包含负权环
return flag;
}
int main(){
int t;
cin>>t;
while(t--){
int u,v,w;
cin>>n>>m;
node=0;
memset(head,0,sizeof head);
for(register int i=1;i<=m;++i){
cin>>u>>v>>w;
add_edge(u,v,w);
if(w>=0){
add_edge(v,u,w);
}
}
if(bellmanford(1)){
puts("YES");//puts:输出并自动空行
}
else puts("NO");
}
return 0;
}
这里空空如也
有帮助，赞一个