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

时间：2024-11-11 07:11:16

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个元素时，新加入的元素如果大于最小的顶端数据，则将其加入并丢掉顶端数据），可以高效地解决这个问题。
  • 合并多个有序数组：通过将每个数组的首个元素放入堆中，每次取出最小值并将其所在数组的下一个元素加入堆中，可以高效地完成合并。

代码实现

import java.util.*;

//边的结构：节点和节点间的权重
class Edge{
    int to,val;
    Edge(int to,int val){
        this.to=to;
        this.val=val;
    }
}

//距离对的结构：节点和节点到源点的距离
class Pair{
    int first,second;
    Pair(int first,int second){
        this.first=first;
        this.second=second;
    }
}

//重写comparator类作为接口
class MyComparition implements Comparator<Pair>{
    @Override
    public int compare(Pair l,Pair r){
        return Integer.compare(l.second,r.second);
    }
    
}

public class Main{
    public static void main (String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int m=scan.nextInt();
        List<List<Edge>> grid=new ArrayList<>(n+1);
        for(int i=0;i<=n;i++){
            grid.add(new ArrayList<>());
        }
        for(int i=0;i<m;i++){
            int s=scan.nextInt();
            int t=scan.nextInt();
            int k=scan.nextInt();
            grid.get(s).add(new Edge(t,k));
        }
        int[] minDist=new int[n+1];
        Arrays.fill(minDist,Integer.MAX_VALUE);
        boolean[] visited=new boolean[n+1];
        
        //源点到源点的距离为0
        minDist[1]=0;
        
        PriorityQueue<Pair> pq=new PriorityQueue<>(new MyComparition());
        pq.add(new Pair(1,0));
        while(!pq.isEmpty()){
            Pair cur=pq.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.val<minDist[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.from=from;
       this.to=to;
       this.val=val;
   }
}

class Main{
   public static void main (String[] args) {
       Scanner scan=new Scanner(System.in);
       int n=scan.nextInt();
       int m=scan.nextInt();
       List<Edge> edges=new ArrayList<>();
       for(int i=0;i<m;i++){
           int from=scan.nextInt();
           int to=scan.nextInt();
           int val=scan.nextInt();
           edges.add(new Edge(from,to,val));
       }
       int[] minDist=new int[n+1];
       Arrays.fill(minDist,Integer.MAX_VALUE);
       minDist[1]=0;
       //进行n-1次松弛
       for(int i=1;i<n;i++){
           for(Edge edge: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]);
   }
}

相关文章