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

代码实现

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>{@Overridepublic 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];//源点到源点的距离为0minDist[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]);}
}