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