代码随想录Day51图dijkstra堆优化版_Bellman_ford 算法dijkstra堆优化版题目小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。小明的起点是第一个车站终点是最后一个车站。然而途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素如天气变化等不同这些因素都会影响每条路径的通行时间。小明希望能选择一条花费时间最少的路线以确保他能够尽快到达目的地。输入描述第一行包含两个正整数第一个正整数 N 表示一共有 N 个公共汽车站第二个正整数 M 表示有 M 条公路。接下来为 M 行每行包括三个整数S、E 和 V代表了从 S 车站可以单向直达 E 车站并且需要花费 V 单位的时间。输出描述输出一个整数代表小明从起点到终点所花费的最小时间。链接https://kamacoder.com/problempage.php?pid1047朴素版的dijkstra是从节点角度去做的如果是稀疏图很多节点很少的边那么空间就会造成浪费。图的存储方式邻接矩阵使用二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图有多少节点就申请多大的二维数组。这种表达方式邻接矩阵在边少节点多的情况下会导致申请过大的二维数组造成空间浪费。而且在寻找节点链接情况的时候需要遍历整个矩阵即 n * n 的时间复杂度同样造成时间浪费。邻接表使用 数组 链表的方式来表示。 邻接表是从边的数量来表示图有多少边 才会申请对应大小的链表。本题从边的角度出发在处理三部曲里的第一步选源点到哪个节点近且该节点未被访问过的时候可以不用去遍历所有节点了。直接把边带权值加入到小顶堆利用堆来自动排序那么每次我们从堆顶里取出边自然就是距离源点最近的节点所在的边。用邻接表来存储邻接表用数组链表来表示ListList grid new ArrayList(n 1);但是本题中边是有权值的权值怎么表示那么里面的链表就不能使用int了而是需要一个键值对来存两个数字一个数表示节点一个数表示指向该节点的这条边的权值ListListpairint,int grid但是在代码中使用 pairint, int 很容易让我们搞混了第一个int 表示什么第二个int表示什么导致代码可读性很差。那么可以定义一个类来取代 pairint, intclassEdge{intto;// 邻接顶点intval;// 边的权重Edge(intto,intval){this.toto;this.valval;}}堆优化细节思路依然是 dijkstra 三部曲第一步选源点到哪个节点近且该节点未被访问过。第二步该最近节点被标记访问过。第三步更新非访问节点到源点的距离即更新minDist数组。第一步之前是通过遍历节点来遍历边通过两层for循环来寻找距离源点最近节点。这次我们直接遍历边且通过堆来对边进行排序达到直接选择距离源点最近节点。我们要选择距离源点近的节点即该边的权值最小所以我们需要一个小顶堆来帮我们对边的权值排序每次从小顶堆堆顶取边就是权值最小的边。有了小顶堆自动对边的权值排序那我们只需要直接从堆里取堆顶元素小顶堆中最小的权值在上面就可以取到离源点最近的节点了 未访问过的节点不会加到堆里进行排序第二步该最近节点被标记访问过这个就是将节点做访问标记和朴素dijkstra一样。第三步更新非访问节点到源点的距离这里的思路也是和朴素dijkstra一样的。朴素版本是这样做的//更新非访问节点到源点的距离即更新minDist数组for(intv1;vn;v){if(!visited[v]grid[cur][v]!INT_MAXminDist[cur]grid[cur][v]minDist[v]){minDist[v]minDist[cur]grid[cur][v];}}其中for循环是为了找到节点cur 链接指向了哪些节点因为使用邻接矩阵的表达方式 所以把所有节点遍历一遍。在邻接表中我们要获取节点cur 链接指向哪些节点就是遍历 grid[cur节点编号] 这个链表。堆优化版本和朴素版本的区别邻接表的表示方式不同。使用优先级队列小顶堆来对新链接的边排序。importjava.util.*;classEdge{intto;//邻接顶点intval;//边的权重Edge(intto,intval){this.toto;this.valval;}}classPairU,V{publicfinalUfirst;publicfinalVsecond;publicPair(Ufirst,Vsecond){this.firstfirst;this.secondsecond;}}classMycomparsionimplementsComparatorPairInteger,Integer{publicintcompare(PairInteger,Integerlhs,PairInteger,Integerrhs){returnInteger.compare(lhs.second,rhs.second);}}publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();ListListEdgegridnewArrayList(n1);for(inti0;in;i){grid.add(newArrayList());}for(inti0;im;i){intp1sc.nextInt();intp2sc.nextInt();intvalsc.nextInt();grid.get(p1).add(newEdge(p2,val));}intstart1;intendn;int[]mindistnewint[n1];Arrays.fill(mindist,Integer.MAX_VALUE);boolean[]visitednewboolean[n1];// 优先队列中存放 Pair节点源点到该节点的权值PriorityQueuePairInteger,IntegerpqnewPriorityQueue(newMycomparsion());pq.add(newPair(start,0));// 初始化队列源点到源点的距离为0所以初始为0mindist[start]0;//起始点到自身的距离为0while(!pq.isEmpty()){PairInteger,Integercurpq.poll();if(visited[cur.first])continue;visited[cur.first]true;for(Edgeedge:grid.get(cur.first)){// 遍历 cur指向的节点cur指向的节点为 edge// cur指向的节点edge.to这条边的权值为 edge.valif(!visited[edge.to]mindist[cur.first]edge.valmindist[edge.to]){// 更新minDistmindist[edge.to]mindist[cur.first]edge.val;pq.add(newPair(edge.to,mindist[edge.to]));}}}if(mindist[end]Integer.MAX_VALUE){System.out.println(-1);// 不能到达终点}else{System.out.println(mindist[end]);// 到达终点最短路径}}}Bellman_ford 算法题目某国为促进城市间经济交流决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市通过道路网络连接网络中的道路仅允许从某个城市单向通行到另一个城市不能反向通行。网络中的道路都有各自的运输成本和政府补贴道路的权值计算方式为运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用权值为负则表示政府的补贴超过了支出的运输成本实际表现为运输过程中还能赚取一定的收益。请找出从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本。如果最低运输成本是一个负数它表示在遵循最优路径的情况下运输过程中反而能够实现盈利。城市 1 到城市 n 之间可能会出现没有路径的情况同时保证道路网络中不存在任何负权回路。负权回路是指一系列道路的总权值为负这样的回路使得通过反复经过回路中的道路理论上可以无限地减少总成本或无限地增加总收益。输入描述第一行包含两个正整数第一个正整数 n 表示该国一共有 n 个城市第二个整数 m 表示这些城市中共有 m 条道路。接下来为 m 行每行包括三个整数s、t 和 v表示 s 号城市运输货物到达 t 号城市道路权值为 v单向图。输出描述如果能够从城市 1 到连通到城市 n 请输出一个整数表示运输成本。如果该整数是负数则表示实现了盈利。如果从城市 1 没有路径可达城市 n请输出 “unconnected”。链接https://kamacoder.com/problempage.php?pid1152本题依然是单源最短路问题求从节点1 到节点n的最小费用。 但本题不同之处在于边的权值是有负数了。Bellman_ford算法的核心思想是对所有边进行松弛n-1次操作n为节点数量从而求得目标最短路。什么是对边进行松弛举例minDist[B] 表示到达B节点最小权值minDist[B] 有哪些状态可以推出来状态一 minDist[A] value 可以推出 minDist[B] 。状态二 minDist[B]本身就有权值 可能是其他边链接的节点B 例如节点C以至于 minDist[B]记录了其他边到minDist[B]的权值minDist[B] 如何取舍。本题我们要求最小权值那么这两个状态我们就取最小的if (minDist[B] minDist[A] value) minDist[B] minDist[A] value。也就是说如果通过 A 到 B 这条边可以获得更短的到达B节点的路径即如果 minDist[B] minDist[A] value那么我们就更新 minDist[B] minDist[A] value 这个过程就叫做 “松弛” 。模拟过程使用minDist数组来表达起点到各个节点的最短距离。起点为节点1 起点到起点的距离为0所以 minDist[1] 初始化为0。对所有边进行第一次松弛示例给出的所有边为5 6 -21 2 15 3 12 5 22 4 -34 6 41 3 5节点5 - 节点6权值为-2 minDist[5] 还是默认数值max所以不能基于节点5去更新节点6。节点1 - 节点2权值为1 minDist[2] minDist[1] 1 更新 minDist[2] minDist[1] 1 0 1 1。节点5 - 节点3权值为1 minDist[5] 还是默认数值max所以不能基于节点5去更新节点3。节点2 - 节点5权值为2 minDist[5] minDist[2] 2 经过上面的计算minDist[2]已经不是默认值而是 1更新 minDist[5] minDist[2] 2 1 2 3。节点2 - 节点4权值为-3 minDist[4] minDist[2] (-3)更新 minDist[4] minDist[2] (-3) 1 (-3) -2节点4 - 节点6权值为4 minDist[6] minDist[4] 4更新 minDist[6] minDist[4] 4 -2 4 2节点1 - 节点3权值为5 minDist[3] minDist[1] 5更新 minDist[3] minDist[1] 5 0 5 5以上是对所有边进行一次松弛之后的结果。对所有边松弛一次相当于计算 起点到达 与起点一条边相连的节点 的最短距离。上面的距离中我们得到里 起点达到 与起点一条边相邻的节点2 和 节点3 的最短距离分别是 minDist[2] 和 minDist[3]。再回归刚刚的问题需要对所有边松弛几次才能得到 起点节点1 到终点节点6的最短距离呢节点数量为n那么起点到终点最多是 n-1 条边相连。那么无论图是什么样的边是什么样的顺序我们对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离。其实也同时计算出了起点 到达 所有节点的最短距离因为所有节点与起点连接的边数最多也就是 n-1 条边。Bellman_ford 的核心算法思路共有两个关键点“松弛”究竟是个啥为什么要对所有边松弛 n - 1 次 n为节点个数importjava.util.*;publicclassMain{staticclassEdge{intfrom;intto;intval;publicEdge(intfrom,intto,intval){this.fromfrom;this.toto;this.valval;}}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();ListEdgeedgesnewArrayList();for(inti0;im;i){intfromsc.nextInt();inttosc.nextInt();intvalsc.nextInt();edges.add(newEdge(from,to,val));}int[]mindistnewint[n1];Arrays.fill(mindist,Integer.MAX_VALUE);mindist[1]0;for(inti1;in;i){//松弛n-1次for(Edgeedge:edges){if(mindist[edge.from]!Integer.MAX_VALUE(mindist[edge.from]edge.val)mindist[edge.to]){mindist[edge.to]mindist[edge.from]edge.val;}}}if(mindist[n]Integer.MAX_VALUE){System.out.println(unconnected);}else{System.out.println(mindist[n]);}}}