算法打卡：第十一章图论part10

今日收获：Bellman_ford 队列优化算法（又名SPFA），bellman_ford之判断负权回路和单源有限最短路

1. Bellman_ford 队列优化算法（又名SPFA）

题目链接：94. 城市间货物运输 I (kamacoder.com)

思路：上篇文章中Bellman_ford算法是在每一次循环中对所有边进行松弛操作。实际上只需要对上一次更新的节点相连边进行松弛操作，可以使用队列来优化。

方法：

java">import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);// 接收数据int n=sc.nextInt();int m=sc.nextInt();List<List<Edge>> grid=new ArrayList<>(n+1);for (int i=0;i<n+1;i++){grid.add(new ArrayList<>());}for (int i=0;i<m;i++){int s=sc.nextInt();int t=sc.nextInt();int v=sc.nextInt();grid.get(s).add(new Edge(s,t,v));}// 初始化minDistint[] minDist=new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]=0;// 存储已更新节点相连的点Queue<Integer> queue=new LinkedList<>();queue.add(1);// 判断节点是否已经在队列中boolean[] inQueue=new boolean[n+1];while (!queue.isEmpty()){int cur=queue.poll();inQueue[cur]=false;for (Edge edge:grid.get(cur)){if (minDist[cur]+edge.val<minDist[edge.to]){minDist[edge.to]=minDist[cur]+edge.val;if (!inQueue[edge.to]){queue.offer(edge.to);inQueue[edge.to]=true;}}}}if (minDist[n]!=Integer.MAX_VALUE){System.out.println(minDist[n]);}else {System.out.println("unconnected");}}
}class Edge{int from;int to;int val;public Edge(int from,int to,int val){this.from=from;this.to=to;this.val=val;}
}

2. bellman_ford之判断负权回路

题目链接：95. 城市间货物运输 II (kamacoder.com)

思路：这道题中出现了负权回路。在没有负权回路的图中，松弛 n 次以上，结果不会有变化；但在有负权回路的情况下，如果松弛 n 次，结果就会有变化了，因为有负权回路可以无限最短路径（一直绕圈，就可以一直得到无限小的最短距离）。

（1）如果没有用队列优化，则松弛n次看终点的成本会不会变化

（2）如果用队列优化的版本，假设每个节点和所有的节点相连则有n-1条边，每个节点最多放入队列n-1次。如果有优先队列则存在节点被放入队列n次

方法：

java">import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);// 接收数据int n=sc.nextInt();int m=sc.nextInt();List<List<Edge>> grid=new ArrayList<>(n+1);for (int i=0;i<n+1;i++){grid.add(new ArrayList<>());}for (int i=0;i<m;i++){int s=sc.nextInt();int t=sc.nextInt();int v=sc.nextInt();grid.get(s).add(new Edge(s,t,v));}// 初始化minDistint[] minDist=new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]=0;// 存储已更新节点相连的点Queue<Integer> queue=new LinkedList<>();queue.add(1);// 判断节点是否已经在队列中boolean[] inQueue=new boolean[n+1];// 记录节点加入队列的次数int[] count=new int[n+1];count[1]++;// 是否存在负权回路boolean flag=false;while (!queue.isEmpty()){int cur=queue.poll();inQueue[cur]=false;for (Edge edge:grid.get(cur)){if (minDist[cur]+edge.val<minDist[edge.to]){minDist[edge.to]=minDist[cur]+edge.val;if (!inQueue[edge.to]){queue.offer(edge.to);inQueue[edge.to]=true;count[edge.to]++;}if (count[edge.to]==n){flag=true;while (!queue.isEmpty()){  // 结束内外层循环queue.poll();}break;}}}}if (flag){System.out.println("circle");return;}if (minDist[n]!=Integer.MAX_VALUE){System.out.println(minDist[n]);}else {System.out.println("unconnected");}}
}class Edge{int from;int to;int val;public Edge(int from,int to,int val){this.from=from;this.to=to;this.val=val;}
}

3. bellman_ford之单源有限最短路

题目链接：96. 城市间货物运输 III (kamacoder.com)

思路：因为最多可以经过k个城市，所以对所有边进行k+1次松弛操作。每一次松弛操作都要基于上一次松弛操作的结果（这个目前不明白，先这样写吧，之后填坑。讲解在这里代码随想录）

方法：

java">import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();// 存储边List<Edge> edges=new ArrayList<>(m);for (int i=0;i<m;i++){int s=sc.nextInt();int t=sc.nextInt();int v=sc.nextInt();edges.add(new Edge(s,t,v));}int src=sc.nextInt();int dst=sc.nextInt();int k=sc.nextInt();// minDist数组和初始化int[] minDist=new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[src]=0;int[] copy=new int[n+1];for (int i=0;i<k+1;i++){  // k+1次松弛边copy=Arrays.copyOf(minDist,n+1);for (Edge edge:edges){if (copy[edge.from]!=Integer.MAX_VALUE&&copy[edge.from]+edge.val<minDist[edge.to]){minDist[edge.to]=copy[edge.from]+edge.val;}}}if (minDist[dst]==Integer.MAX_VALUE){System.out.println("unreachable");}else {System.out.println(minDist[dst]);}}
}class Edge{int from;int to;int val;public Edge(int from,int to,int val){this.from=from;this.to=to;this.val=val;}
}