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

参考文章均来自代码随想录Bellman_ford 队列优化算法参考文章链接对第 59天中的题目进行优化 详细见参考文章推理步骤还是用邻接表#includeiostream#includevector#includequeue#includelist#includeclimitsusingnamespacestd;structEdge{//邻接表intto;// 链接的节点intval;// 边的权重Edge(intt,intw):to(t),val(w){}// 构造函数};intmain(){intn,m,p1,p2,val;cinnm;vectorlistEdgegrid(n1);vectorboolisInQueue(n1);// 加入优化已经在队里里的元素不用重复添加// 将所有边保存起来for(inti0;im;i){cinp1p2val;// p1 指向 p2权值为 valgrid[p1].push_back(Edge(p2,val));}intstart1;// 起点intendn;// 终点vectorintminDist(n1,INT_MAX);minDist[start]0;queueintque;que.push(start);while(!que.empty()){intnodeque.front();que.pop();isInQueue[node]false;// 从队列里取出的时候要取消标记我们只保证已经在队列里的元素不用重复加入for(Edge edge:grid[node]){intfromnode;inttoedge.to;intvalueedge.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)coutunconnectedendl;// 不能到达终点elsecoutminDist[end]endl;// 到达终点最短路径}Bellman_ford之判断负权回路参考文章链接题目链接有负权回路的情况下一直都会有更短的最短路所以 松弛 第n次minDist数组 也会发生改变。那么解决本题的 核心思路就是在 kama94.城市间货物运输I 的基础上再多松弛一次看minDist数组 是否发生变化。#includeiostream#includevector#includelist#includeclimitsusingnamespacestd;intmain(){intn,m,p1,p2,val;cinnm;vectorvectorintgrid;for(inti0;im;i){cinp1p2val;// p1 指向 p2权值为 valgrid.push_back({p1,p2,val});}intstart1;// 起点intendn;// 终点vectorintminDist(n1,INT_MAX);minDist[start]0;boolflagfalse;for(inti1;in;i){// 这里我们松弛n次最后一次判断负权回路for(vectorintside:grid){intfromside[0];inttoside[1];intpriceside[2];if(in){if(minDist[from]!INT_MAXminDist[to]minDist[from]price)minDist[to]minDist[from]price;}else{// 多加一次松弛判断负权回路if(minDist[from]!INT_MAXminDist[to]minDist[from]price)flagtrue;}}}if(flag)coutcircleendl;elseif(minDist[end]INT_MAX){coutunconnectedendl;}else{coutminDist[end]endl;}}bellman_ford之单源有限最短路参考文章链接题目链接题目中描述是 最多经过 k 个城市的条件下而不是一定经过k个城市也可以经过的城市数量比k小但要最短的路径对所有边松弛一次相当于计算 起点到达 与起点一条边相连的节点 的最短距离本题是最多经过 k 个城市 那么是 k 1条边相连的节点bellman_ford 标准写法是松弛 n-1 次本题就松弛 k 1次就好#includeiostream#includevector#includelist#includeclimitsusingnamespacestd;intmain(){intsrc,dst,k,p1,p2,val,m,n;cinnm;vectorvectorintgrid;for(inti0;im;i){cinp1p2val;grid.push_back({p1,p2,val});}cinsrcdstk;vectorintminDist(n1,INT_MAX);minDist[src]0;vectorintminDist_copy(n1);// 用来记录上一次遍历的结果for(inti1;ik1;i){minDist_copyminDist;// 获取上一次计算的结果for(vectorintside:grid){intfromside[0];inttoside[1];intpriceside[2];// 注意使用 minDist_copy 来计算 minDistif(minDist_copy[from]!INT_MAXminDist[to]minDist_copy[from]price){minDist[to]minDist_copy[from]price;}}}if(minDist[dst]INT_MAX)coutunreachableendl;// 不能到达终点elsecoutminDist[dst]endl;// 到达终点最短路径}