Day60 图论part10

本日大家会感受到 Bellman_ford 算法系列在差别场景下的应用。

  

建议依然是：一刷的时候，能理解 原理，知道Bellman_ford 办理差别场景的题目 ，照着代码随想录能抄下来代码就好，就算达标。 二刷的时候自己尝试独立去写，三刷的时候 才能有肯定深度理解各个最短路算法。

  

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

  

代码随想录

1. import java.util.*;
3. public class Main{
4.     public static void main (String[] args) {
5.         //对所有的边松弛n-1次
6.         Scanner scanner = new Scanner(System.in);
7.         int n = scanner.nextInt();
8.         int m = scanner.nextInt();
9.         List<List<Edge>> graph = new ArrayList<>(n+1);
10.         
11.         for(int i = 0; i <= n; i++){
12.             graph.add(new ArrayList<>());
13.         }
14.         
15.         for(int i = 0; i < m; i++){
16.             int start = scanner.nextInt();
17.             int end = scanner.nextInt();
18.             int val = scanner.nextInt();
19.             graph.get(start).add(new Edge(start, end, val));
20.         }
21.         
22.         int[] minDist = new int[n+1];
23.         Arrays.fill(minDist, Integer.MAX_VALUE);
24.         minDist[1] = 0;
25.         
26.         Deque<Integer> queue = new ArrayDeque<>();
27.         boolean[] isVisited = new boolean[n+1];
28.         queue.add(1);
29.         isVisited[1] = true;
30.         
31.         while(!queue.isEmpty()){
32.             int start = queue.remove();
33.             //取出队列的时候，要取消标记，这样保证有其他路径对该节点进行更新，我们只要保证节点不被重复加入队列即可
34.             isVisited[start] = false;
35.             
36.             for(Edge edge : graph.get(start)){
37.                 if(minDist[start] + edge.val < minDist[edge.end]){
38.                     minDist[edge.end] = minDist[start] + edge.val;
39.                    if(!isVisited[edge.end]){
40.                     queue.add(edge.end);
41.                     isVisited[edge.end] = true;
42.                     }
43.                 }
44.                
45.             }
46.         }
47.         
48.         if(minDist[n] == Integer.MAX_VALUE){
49.             System.out.println("unconnected");
50.         }else{
51.             System.out.println(minDist[n]);
52.         }
53.    
54.     }
55. }
57. class Edge{
58.     int start;
59.     int end;
60.     int val;
61.    
62.     public Edge(int start, int end, int val){
63.         this.start = start;
64.         this.end = end;
65.         this.val = val;
66.     }
67. }

复制代码

总结
  1.普通的Bellman_ford算法其实是每次都对所有的边都举行一次松懈，但其实但真正有效的松懈，是基于已经盘算过的节点在做的松懈。所以我们每次松懈只必要基于上一次松懈更新过的节点，以该节点作为出发节点对毗连的边就行。那我们就可以使用队列来纪录上一次松懈更新过的节点，把这些节点依次加入到队列内里，然后又取出来处理惩罚。
  2.队列内里存储的是每条边的起点，我们必要根据这些起点，找到边，所以这样传统的邻接表来存储图是最好的List<List<Edge>> graph = new ArrayList<>(n+1);
  3.然后在while循环内里，还有一些地方和之前的处理惩罚不一样，我们必要使用isVisited[]数组来判断节点是否在队列内里&#x

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