当前位置：首页 > news >正文

代码随想录算法训练营第六十天|Bellman_ford 队列优化算法、Bellman_ford之判断负权回路、bellman_ford之单源有限最短路

news 2026/5/24 23:21:01

参考文章均来自代码随想录

Bellman_ford 队列优化算法

参考文章链接

对第 59天中的题目进行优化详细见参考文章推理步骤
还是用邻接表

#include<iostream>#include<vector>#include<queue>#include<list>#include<climits>usingnamespacestd;structEdge{//邻接表intto;// 链接的节点intval;// 边的权重Edge(intt,intw):to(t),val(w){}// 构造函数};intmain(){intn,m,p1,p2,val;cin>>n>>m;vector<list<Edge>>grid(n+1);vector<bool>isInQueue(n+1);// 加入优化，已经在队里里的元素不用重复添加// 将所有边保存起来for(inti=0;i<m;i++){cin>>p1>>p2>>val;// p1 指向 p2，权值为 valgrid[p1].push_back(Edge(p2,val));}intstart=1;// 起点intend=n;// 终点vector<int>minDist(n+1,INT_MAX);minDist[start]=0;queue<int>que;que.push(start);while(!que.empty()){intnode=que.front();que.pop();isInQueue[node]=false;// 从队列里取出的时候，要取消标记，我们只保证已经在队列里的元素不用重复加入for(Edge edge:grid[node]){intfrom=node;intto=edge.to;intvalue=edge.val;if(minDist[to]>minDist[from]+value){// 开始松弛minDist[to]=minDist[from]+value;if(isInQueue[to]==false){// 已经在队列里的元素不用重复添加que.push(to);isInQueue[to]=true;}}}}if(minDist[end]==INT_MAX)cout<<"unconnected"<<endl;// 不能到达终点elsecout<<minDist[end]<<endl;// 到达终点最短路径}

Bellman_ford之判断负权回路

参考文章链接

题目链接

有负权回路的情况下，一直都会有更短的最短路，所以松弛第n次，minDist数组也会发生改变。

那么解决本题的核心思路，就是在 kama94.城市间货物运输I 的基础上，再多松弛一次，看minDist数组是否发生变化。

#include<iostream>#include<vector>#include<list>#include<climits>usingnamespacestd;intmain(){intn,m,p1,p2,val;cin>>n>>m;vector<vector<int>>grid;for(inti=0;i<m;i++){cin>>p1>>p2>>val;// p1 指向 p2，权值为 valgrid.push_back({p1,p2,val});}intstart=1;// 起点intend=n;// 终点vector<int>minDist(n+1,INT_MAX);minDist[start]=0;boolflag=false;for(inti=1;i<=n;i++){// 这里我们松弛n次，最后一次判断负权回路for(vector<int>&side:grid){intfrom=side[0];intto=side[1];intprice=side[2];if(i<n){if(minDist[from]!=INT_MAX&&minDist[to]>minDist[from]+price)minDist[to]=minDist[from]+price;}else{// 多加一次松弛判断负权回路if(minDist[from]!=INT_MAX&&minDist[to]>minDist[from]+price)flag=true;}}}if(flag)cout<<"circle"<<endl;elseif(minDist[end]==INT_MAX){cout<<"unconnected"<<endl;}else{cout<<minDist[end]<<endl;}}

bellman_ford之单源有限最短路

参考文章链接

题目链接

题目中描述是最多经过 k 个城市的条件下，而不是一定经过k个城市，也可以经过的城市数量比k小，但要最短的路径

对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离

本题是最多经过 k 个城市，那么是 k + 1条边相连的节点

bellman_ford 标准写法是松弛 n-1 次，本题就松弛 k + 1次就好

#include<iostream>#include<vector>#include<list>#include<climits>usingnamespacestd;intmain(){intsrc,dst,k,p1,p2,val,m,n;cin>>n>>m;vector<vector<int>>grid;for(inti=0;i<m;i++){cin>>p1>>p2>>val;grid.push_back({p1,p2,val});}cin>>src>>dst>>k;vector<int>minDist(n+1,INT_MAX);minDist[src]=0;vector<int>minDist_copy(n+1);// 用来记录上一次遍历的结果for(inti=1;i<=k+1;i++){minDist_copy=minDist;// 获取上一次计算的结果for(vector<int>&side:grid){intfrom=side[0];intto=side[1];intprice=side[2];// 注意使用 minDist_copy 来计算 minDistif(minDist_copy[from]!=INT_MAX&&minDist[to]>minDist_copy[from]+price){minDist[to]=minDist_copy[from]+price;}}}if(minDist[dst]==INT_MAX)cout<<"unreachable"<<endl;// 不能到达终点elsecout<<minDist[dst]<<endl;// 到达终点最短路径}