day58 图论章节刷题Part09（dijkstra(堆优化版)、Bellman_ford 算法） ...

dijkstra(堆优化版)

朴素版的dijkstra解法的时间复杂度为 O(n^2)，时间复杂度只和 n（节点数量）有关系。如果n很大的话，可以从边的角度来考虑。因为是稀疏图，从边的角度考虑的话，我们在堆优化算法中最好使用毗邻表来存储图，如许不会造成空间的浪费。同时直接遍历边，通过堆（小顶堆）对边举行排序，选择距离源点最近的节点。
时间复杂度：O(ElogE) ，E 为边的数量- logE是小顶堆的时间复杂度
空间复杂度：O(N + E) ，N 为节点的数量，毗邻表：O(n+e)、最短距离数组：O(n)、访问标志数组：O(n)、优先队列：O(n)
之前在求top K题目时应用过小顶堆，这里再复习一下。
小顶堆

小顶堆是一种特殊的完全二叉树，其中每个父节点的值都不大于其子节点的值。这种特性使得堆的根节点始终是堆中的最小值，非常得当用于实现优先队列等数据结构。
创建一个优先队列，并举行维护
PriorityQueue priorityQueue = new PriorityQueue<>();
题目应用：

• 求解 Top K 题目：小顶堆可以用于求解 Top K 题目，即从 N 个元素中找出最大的 K 个元素。通过维护一个大小为 K 的小顶堆（当小顶堆中已经有K个元素时，新参加的元素如果大于最小的顶端数据，则将其参加并丢掉顶端数据），可以高效地办理这个题目。
  
• 合并多个有序数组：通过将每个数组的首个元素放入堆中，每次取出最小值并将其所在数组的下一个元素参加堆中，可以高效地完成合并。
  

代码实现

1. import java.util.*;
3. //边的结构：节点和节点间的权重
4. class Edge{
5.     int to,val;
6.     Edge(int to,int val){
7.         this.to=to;
8.         this.val=val;
9.     }
10. }
12. //距离对的结构：节点和节点到源点的距离
13. class Pair{
14.     int first,second;
15.     Pair(int first,int second){
16.         this.first=first;
17.         this.second=second;
18.     }
19. }
21. //重写comparator类作为接口
22. class MyComparition implements Comparator<Pair>{
23.     @Override
24.     public int compare(Pair l,Pair r){
25.         return Integer.compare(l.second,r.second);
26.     }
27.    
28. }
30. public class Main{
31.     public static void main (String[] args) {
32.         Scanner scan=new Scanner(System.in);
33.         int n=scan.nextInt();
34.         int m=scan.nextInt();
35.         List<List<Edge>> grid=new ArrayList<>(n+1);
36.         for(int i=0;i<=n;i++){
37.             grid.add(new ArrayList<>());
38.         }
39.         for(int i=0;i<m;i++){
40.             int s=scan.nextInt();
41.             int t=scan.nextInt();
42.             int k=scan.nextInt();
43.             grid.get(s).add(new Edge(t,k));
44.         }
45.         int[] minDist=new int[n+1];
46.         Arrays.fill(minDist,Integer.MAX_VALUE);
47.         boolean[] visited=new boolean[n+1];
48.         
49.         //源点到源点的距离为0
50.         minDist[1]=0;
51.         
52.         PriorityQueue<Pair> pq=new PriorityQueue<>(new MyComparition());
53.         pq.add(new Pair(1,0));
54.         while(!pq.isEmpty()){
55.             Pair cur=pq.poll();
56.             if(visited[cur.first]) continue;
57.             else visited[cur.first]=true;
58.             for(Edge edge:grid.get(cur.first)){
59.                 if(!visited[edge.to] && minDist[cur.first]+edge.val<minDist[edge.to])
60.                     minDist[edge.to]=minDist[cur.first]+edge.val;
61.                     pq.add(new Pair(edge.to,minDist[edge.to]));
62.             }
63.         }
64.         
65.         if(minDist[n]!=Integer.MAX_VALUE) System.out.println(minDist[n]);
66.         else System.out.println(-1);
67.         
68.     }
69. }

复制代码

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 算法则相当于不断的累加路径，如果新的路径小于原值就更新。
代码如下：

1. import java.util.*;
2. class Edge{
3.    int from,to,val;
4.    public Edge(int from,int to,int val){
5.        this.from=from;
6.        this.to=to;
7.        this.val=val;
8.    }
9. }
11. class Main{
12.    public static void main (String[] args) {
13.        Scanner scan=new Scanner(System.in);
14.        int n=scan.nextInt();
15.        int m=scan.nextInt();
16.        List<Edge> edges=new ArrayList<>();
17.        for(int i=0;i<m;i++){
18.            int from=scan.nextInt();
19.            int to=scan.nextInt();
20.            int val=scan.nextInt();
21.            edges.add(new Edge(from,to,val));
22.        }
23.        int[] minDist=new int[n+1];
24.        Arrays.fill(minDist,Integer.MAX_VALUE);
25.        minDist[1]=0;
26.        //进行n-1次松弛
27.        for(int i=1;i<n;i++){
28.            for(Edge edge:edges){
29.                if(minDist[edge.from]!=Integer.MAX_VALUE && minDist[edge.from]+edge.val<minDist[edge.to]){
30.                    minDist[edge.to]=minDist[edge.from]+edge.val;
31.                }
32.            }
33.        }
34.        if(minDist[n]==Integer.MAX_VALUE) System.out.println("unconnected");
35.        else System.out.println(minDist[n]);
36.    }
37. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。