力扣算法刷题 Day 63 Bellman_ford 算法

队列优化Bellman_ford 朴素算法在每一轮操作中对所有边进行松弛是不必要的。只需要对上一轮更新过的边进行计算就好因此我们定义一个队列初始化只有出发节点之后其中为当前轮次加入的队列。#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;// 到达终点最短路径}负权回路判断松弛第n次如果minDist数组发生变化则说明存在负权回路。正常情况下第N-1次即已经完成。#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;}}单源限制经过边的条数设最多经过k个节点则共k2个节点。那么我们松弛k1次就好。此外还需要基于上一次松弛的结果来更新当前轮次松弛的结果这样才能真正的限制。#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;// 到达终点最短路径}