今天大家会感受到 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