Bellman_ford算法的核心思想是 對所有邊進行松弛n-1次操作（n為節點數量），從而求得目標最短路。

其實 Bellman_ford算法 也是采用了動態規劃的思想，即：將一個問題分解成多個決策階段，通過狀態之間的遞歸關系最后計算出全局最優解。

Bellman_ford 是可以計算 負權值的單源最短路算法。

其算法核心思路是對 所有邊進行 n-1 次 松弛。

方法：Bellman_ford

思路：

核心思路代碼：

if (minDist[e.to] > minDist[e.from] + e.val) minDist[e.to] = minDist[e.from] + e.val;

如果改一改樣子，是不是跟動態規劃很像呢？

minDist[B] = min(minDist[A] + value, minDist[B])

其實松弛操作，就是進行“動態規劃”。因為每更新一個節點的狀態，都會影響其它節點。

所以每更新一個節點，就對全部節點的狀態進行更新。（n個節點，更新n-1一次）

實際上，每更新一個節點，并不一定要更新全部節點的minDist。所以下面會講到優化的方式。

import java.util.*;public class Main {static 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;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();List<Edge> edges = new ArrayList<>();// 將所有邊保存起來for (int i = 0; i < m; i++) {int from = in.nextInt();int to = in.nextInt();int val = in.nextInt();edges.add(new Edge(from, to, val));}int start = 1; // 起點int end = n; // 終點int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;// 對所有邊 松弛 n-1 次（這里遍歷的是節點，從1遍歷到n-1）for (int i = 1; i < n; i++) {// 每一次松弛，都是對所有邊進行松弛for (Edge e : edges) {// 松弛操作if (minDist[e.from] != Integer.MAX_VALUE&& minDist[e.to] > minDist[e.from] + e.val) {minDist[e.to] = minDist[e.from] + e.val;}}}// 不能到達終點if (minDist[end] == Integer.MAX_VALUE) {System.out.println("unconnected");} else {// 到達終點最短路徑（運輸成本最小）System.out.println(minDist[end]);}}
}

不用隊列優化的時候，一旦一個節點更新了，就要刷新整個圖的所有節點的minDist，但是這樣有很多操作是多余的。比如節點1只和2,3相連，就應該只刷新2,3的midDist。我們用隊列記錄“要刷新的節點”，可以減少很多操作。

但是隊列的入隊和出隊也是有性能損耗的，如果是稠密圖，邊比較多，而且互相連接的節點比較多的話，隊列帶來的性能損耗可能會超過原來遍歷節點的損耗。

故此，稀疏圖適合用隊列優化，稠密圖的話，隊列優化效果不明顯，加上隊列操作，還甚至有可能比不優化更加耗時。

方法： 隊列優化的 Bellman_ford（又名SPFA）

思路：

1. 不優化時，由于要遍歷所有的邊，所以直接將所有的邊存起來就好：List<Edge> edges = new ArrayList<>();；隊列優化時，需要用鄰接表保存圖，不然每次就要遍歷找起點from對應的邊了。
2. 隊列記錄，“要刷新的節點”，該節點需要poll出來處理，它所有鄰接的節點的minDist
3. boolean[] isInQue記錄在隊列，已經在隊列的不要重復添加。

import java.util.*;public class Main {static 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;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();List<List<Edge>> graph = new ArrayList<>();for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}// 鄰接表保存圖for (int i = 0; i < m; i++) {int from = in.nextInt();int to = in.nextInt();int val = in.nextInt();graph.get(from).add(new Edge(from, to, val));}int start = 1; // 起點int end = n; // 終點// 存儲從源點到每個節點的最短距離int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;// 隊列記錄，“要刷新的節點”，該節點需要poll出來處理，它所有鄰接的節點的minDistDeque<Integer> que = new ArrayDeque<>();que.offer(start);// 在隊列標志boolean[] isInQue = new boolean[n + 1];while (!que.isEmpty()) {int cur = que.poll();isInQue[cur] = false;for (Edge e : graph.get(cur)) {// 松弛操作if (minDist[e.to] > minDist[e.from] + e.val) {minDist[e.to] = minDist[e.from] + e.val;// 避免重復入隊if (!isInQue[e.to]) {que.offer(e.to);isInQue[e.to] = true;}}}}// 不能到達終點if (minDist[end] == Integer.MAX_VALUE) {System.out.println("unconnected");} else {// 到達終點最短路徑（運輸成本最小）System.out.println(minDist[end]);}}
}

方法：bellman_ford之判斷負權回路

思路：

負權回路的意思：出現環，每走一次環，得出的sum是負數。因為求的是最小值min，所以會一直在這個環轉圈圈。

在 bellman_ford 算法中，松弛 n-1 次所有的邊 就可以求得 起點到任何節點的最短路徑，松弛 n 次以上，minDist數組（記錄起到到其他節點的最短距離）中的結果也不會有改變

而本題有負權回路的情況下，一直都會有更短的最短路，所以 松弛 第n次，minDist數組 也會發生改變。

那么解決本題的 核心思路，就是在 《上題》 的基礎上，再多松弛一次，看minDist數組 是否發生變化。

import java.util.*;public class Main {static 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;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();List<Edge> edges = new ArrayList<>();for (int i = 0; i < m; i++) {int from = in.nextInt();int to = in.nextInt();int val = in.nextInt();edges.add(new Edge(from, to, val));}int start = 1;int end = n;int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;// 這里我們松弛n次，最后一次判斷負權回路boolean circle = false;for (int i = 1; i <= n; i++) {for (Edge e : edges) {if (i < n) {// 照常if (minDist[e.from] != Integer.MAX_VALUE&& minDist[e.to] > minDist[e.from] + e.val) {minDist[e.to] = minDist[e.from] + e.val;}} else {// 多加一次松弛判斷負權回路if (minDist[e.from] != Integer.MAX_VALUE&& minDist[e.to] > minDist[e.from] + e.val) {circle = true;}}}}// 出現負權回路，轉圈圈。if (circle) {System.out.println("circle");} else if (minDist[end] == Integer.MAX_VALUE) {// 不能到達終點System.out.println("unconnected");} else {// 到達終點最短路徑（運輸成本最小）System.out.println(minDist[end]);}}
}

方法： 隊列優化的 Bellman_ford（又名SPFA）

思路：

思路同上，統計是否有節點，遍歷過n次。

如果有，證明存在負權回路，在轉圈圈了，此時，清空隊列，退出循環。

import java.util.*;public class Main {static 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;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();List<List<Edge>> graph = new ArrayList<>();for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}for (int i = 0; i < m; i++) {int from = in.nextInt();int to = in.nextInt();int val = in.nextInt();graph.get(from).add(new Edge(from, to, val));}int start = 1;int end = n;int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;Deque<Integer> que = new ArrayDeque<>();que.offer(start);boolean[] isInQue = new boolean[n + 1];// 統計該節點，入隊的次數int[] countInQue = new int[n + 1];countInQue[start]++;// 是否存在負權回路，轉圈圈的標志boolean circle = false;while (!que.isEmpty()) {int cur = que.poll();isInQue[cur] = false;for (Edge e : graph.get(cur)) {if (minDist[e.to] > minDist[e.from] + e.val) {minDist[e.to] = minDist[e.from] + e.val;// 避免重復入隊if (!isInQue[e.to]) {que.offer(e.to);isInQue[e.to] = true;// 入隊次數+1countInQue[e.to]++;}// 如果有節點入隊n次，證明已經開始轉圈圈，清空隊列，退出循環if (countInQue[e.to] == n) {circle = true;que.clear();break;}}}}// 出現負權回路，轉圈圈。if (circle) {System.out.println("circle");} else if (minDist[end] == Integer.MAX_VALUE) {// 不能到達終點System.out.println("unconnected");} else {// 到達終點最短路徑（運輸成本最小）System.out.println(minDist[end]);}}
}

其關鍵在于本題的兩個因素：

• 本題可以有負權回路，說明只要多做松弛，結果是會變的。
• 本題要求最多經過k個節點，對松弛次數是有限制的。

方法：bellman_ford之單源有限最短路

思路：

最多經過k座城市，加上start和end，就是一共有k+2個城市。所以要遍歷k+1次。

使用minDistCopy記錄上一輪遍歷的結果。

import java.util.*;public class Main {static 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;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();List<Edge> edges = new ArrayList<>();for (int i = 0; i < m; i++) {int from = in.nextInt();int to = in.nextInt();int val = in.nextInt();edges.add(new Edge(from, to, val));}int start = in.nextInt();int end = in.nextInt();// 最多經過k座城市，加上start和end，就是一共有k+2個城市int k = in.nextInt();int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;// 用來記錄上一輪遍歷的結果int[] minDistCopy = new int[n + 1];// 一共有k+2個城市，所以要遍歷k+1遍for (int i = 1; i <= k + 1; i++) {// 復制上一輪遍歷的結果System.arraycopy(minDist, 0, minDistCopy, 0, n + 1);for (Edge e : edges) {if (minDistCopy[e.from] != Integer.MAX_VALUE&& minDist[e.to] > minDistCopy[e.from] + e.val) {minDist[e.to] = minDistCopy[e.from] + e.val;}}}if (minDist[end] == Integer.MAX_VALUE) {// 不能到達終點System.out.println("unreachable");} else {// 到達終點最短路徑（運輸成本最小）System.out.println(minDist[end]);}}
}

方法： 隊列優化的 Bellman_ford（又名SPFA）

思路：

關鍵在于 如何控制松弛k次。可以用一個變量 que_size 記錄每一輪松弛入隊列的所有節點數量。

下一輪松弛的時候，就把隊列里 que_size 個節點都彈出來，就是上一輪松弛入隊列的節點。

import java.util.*;public class Main {static 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;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();List<List<Edge>> graph = new ArrayList<>();for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}for (int i = 0; i < m; i++) {int from = in.nextInt();int to = in.nextInt();int val = in.nextInt();graph.get(from).add(new Edge(from, to, val));}int start = in.nextInt();int end = in.nextInt();// 最多經過k座城市，加上start和end，就是一共有k+2個城市int k = in.nextInt();// 原來要遍歷n-1次，現在有k+2個節點，所以要遍歷k+1次k++;int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;// 用來記錄上一輪遍歷的結果int[] minDistCopy = new int[n + 1];Deque<Integer> que = new ArrayDeque<>();que.offer(start);int queSize = 0;while (k-- > 0 && !que.isEmpty()) {// isInQue標志，每一輪都要初始化一次boolean[] isInQue = new boolean[n + 1];// 復制上一輪遍歷的結果System.arraycopy(minDist, 0, minDistCopy, 0, n + 1);// 這一輪要松弛的個數queSize = que.size();// 開始這一輪while (queSize-- > 0) {int cur = que.poll();isInQue[cur] = false;for (Edge e : graph.get(cur)) {if (minDist[e.to] > minDistCopy[e.from] + e.val) {minDist[e.to] = minDistCopy[e.from] + e.val;if (!isInQue[e.to]) {que.offer(e.to);isInQue[e.to] = true;}}}}}// 不能到達終點if (minDist[end] == Integer.MAX_VALUE) {System.out.println("unreachable");} else {// 到達終點最短路徑（運輸成本最小）System.out.println(minDist[end]);}}
}