Day60 图论part10

今天大家会感受到 Bellman_ford 算法系列在不同场景下的应用。

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

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

代码随想录

import java.util.*;

public class Main{
    public static void main (String[] args) {
        //对所有的边松弛n-1次
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<List<Edge>> graph = new ArrayList<>(n+1);
        
        for(int i = 0; i <= n; i++){
            graph.add(new ArrayList<>());
        }
        
        for(int i = 0; i < m; i++){
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int val = scanner.nextInt();
            graph.get(start).add(new Edge(start, end, val));
        }
        
        int[] minDist = new int[n+1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[1] = 0;
        
        Deque<Integer> queue = new ArrayDeque<>();
        boolean[] isVisited = new boolean[n+1];
        queue.add(1);
        isVisited[1] = true;
        
        while(!queue.isEmpty()){
            int start = queue.remove();
            //取出队列的时候，要取消标记，这样保证有其他路径对该节点进行更新，我们只要保证节点不被重复加入队列即可
            isVisited[start] = false;
            
            for(Edge edge : graph.get(start)){
                if(minDist[start] + edge.val < minDist[edge.end]){
                    minDist[edge.end] = minDist[start] + edge.val;
                   if(!isVisited[edge.end]){
                    queue.add(edge.end);
                    isVisited[edge.end] = true;
                    }
                } 
                
            }
        }
        
        if(minDist[n] == Integer.MAX_VALUE){
            System.out.println("unconnected");
        }else{
            System.out.println(minDist[n]);
        }
    
    }
}

class Edge{
    int start;
    int end;
    int val;
    
    public Edge(int start, int end, int val){
        this.start = start;
        this.end = end;
        this.val = val;
    }
}

总结

1.普通的Bellman_ford算法其实是每次都对所有的边都进行一次松弛，但其实但真正有效的松弛，是基于已经计算过的节点在做的松弛。所以我们每次松弛只需要基于上一次松弛更新过的节点，以该节点作为出发节点对连接的边就行。那我们就可以使用队列来记录上一次松弛更新过的节点，把这些节点依次加入到队列里面，然后又取出来处理。

2.队列里面存储的是每条边的起点，我们需要根据这些起点，找到边，所以这样传统的邻接表来存储图是最好的List<List<Edge>> graph = new ArrayList<>(n+1);

3.然后在while循环里面，还有一些地方和之前的处理不一样，我们需要使用isVisited[]数组来判断节点是否在队列里面&#x