网站建设套餐怎么样,WordPress有评论邮件通知,wordpress充值漏洞,app接入广告变现dijkstra(堆优化版)
朴素版的dijkstra解法的时间复杂度为 O(n^2)#xff0c;时间复杂度只和 n#xff08;节点数量#xff09;有关系。如果n很大的话#xff0c;可以从边的角度来考虑。因为是稀疏图#xff0c;从边的角度考虑的话#xff0c;我们在堆优化算法中最好使用…dijkstra(堆优化版)
朴素版的dijkstra解法的时间复杂度为 O(n^2)时间复杂度只和 n节点数量有关系。如果n很大的话可以从边的角度来考虑。因为是稀疏图从边的角度考虑的话我们在堆优化算法中最好使用邻接表来存储图这样不会造成空间的浪费。同时直接遍历边通过堆小顶堆对边进行排序选择距离源点最近的节点。
时间复杂度O(ElogE) E 为边的数量- logE是小顶堆的时间复杂度 空间复杂度O(N E) N 为节点的数量邻接表O(ne)、最短距离数组O(n)、访问标记数组O(n)、优先队列O(n)
之前在求top K问题时应用过小顶堆这里再复习一下。
小顶堆
小顶堆是一种特殊的完全二叉树其中每个父节点的值都不大于其子节点的值。这种特性使得堆的根节点始终是堆中的最小值非常适合用于实现优先队列等数据结构。
创建一个优先队列并进行维护 PriorityQueue priorityQueue new PriorityQueue();
问题应用
求解 Top K 问题小顶堆可以用于求解 Top K 问题即从 N 个元素中找出最大的 K 个元素。通过维护一个大小为 K 的小顶堆当小顶堆中已经有K个元素时新加入的元素如果大于最小的顶端数据则将其加入并丢掉顶端数据可以高效地解决这个问题。合并多个有序数组通过将每个数组的首个元素放入堆中每次取出最小值并将其所在数组的下一个元素加入堆中可以高效地完成合并。
代码实现
import java.util.*;//边的结构节点和节点间的权重
class Edge{int to,val;Edge(int to,int val){this.toto;this.valval;}
}//距离对的结构节点和节点到源点的距离
class Pair{int first,second;Pair(int first,int second){this.firstfirst;this.secondsecond;}
}//重写comparator类作为接口
class MyComparition implements ComparatorPair{Overridepublic int compare(Pair l,Pair r){return Integer.compare(l.second,r.second);}}public class Main{public static void main (String[] args) {Scanner scannew Scanner(System.in);int nscan.nextInt();int mscan.nextInt();ListListEdge gridnew ArrayList(n1);for(int i0;in;i){grid.add(new ArrayList());}for(int i0;im;i){int sscan.nextInt();int tscan.nextInt();int kscan.nextInt();grid.get(s).add(new Edge(t,k));}int[] minDistnew int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);boolean[] visitednew boolean[n1];//源点到源点的距离为0minDist[1]0;PriorityQueuePair pqnew PriorityQueue(new MyComparition());pq.add(new Pair(1,0));while(!pq.isEmpty()){Pair curpq.poll();if(visited[cur.first]) continue;else visited[cur.first]true;for(Edge edge:grid.get(cur.first)){if(!visited[edge.to] minDist[cur.first]edge.valminDist[edge.to])minDist[edge.to]minDist[cur.first]edge.val;pq.add(new Pair(edge.to,minDist[edge.to]));}}if(minDist[n]!Integer.MAX_VALUE) System.out.println(minDist[n]);else System.out.println(-1);}
}Bellman_ford 算法-94. 城市间货物运输 I
本题依然是单源最短路问题求从节点1 到节点n 的最小费用。 但本题不同之处在于边的权值有负数。
Bellman_ford 算法
Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作n为节点数量从而求得目标最短路。
“松弛”-如果通过A到B这条边可以获得更短的到达B节点的路径即如果 minDist[B] minDist[A] value那么我们就更新 minDist[B] minDist[A] value。
Bellman_ford算法采用了动态规划的思想即将一个问题分解成多个决策阶段通过状态之间的递归关系最后计算出全局最优解。 对所有边松弛一次相当于计算起点到达与起点一条边相连的节点的最短距离。所以需要对所有边松弛n-1次才能得到起点到终点的最短距离。 有一些题目可能不需要n-1次就能找到最短路径但是n-1次能保证找到各类题目从原点到所有点的最短路径
时间复杂度 O(N * E) , N为节点数量E为图中边的数量 空间复杂度 O(N) 即 minDist 数组所开辟的空间
和dijkstra算法的区别是dijkstra算法是从源点开始累加最小路径进行推演的Bellman_ford 算法则相当于不断的累加路径如果新的路径小于原值就更新。
代码如下
import java.util.*;
class Edge{int from,to,val;public Edge(int from,int to,int val){this.fromfrom;this.toto;this.valval;}
}class Main{public static void main (String[] args) {Scanner scannew Scanner(System.in);int nscan.nextInt();int mscan.nextInt();ListEdge edgesnew ArrayList();for(int i0;im;i){int fromscan.nextInt();int toscan.nextInt();int valscan.nextInt();edges.add(new Edge(from,to,val));}int[] minDistnew int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]0;//进行n-1次松弛for(int i1;in;i){for(Edge edge:edges){if(minDist[edge.from]!Integer.MAX_VALUE minDist[edge.from]edge.valminDist[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]);}
}
