94. 城市間貨物運輸| （Bellman_ford隊列優化版 / SPFA）

題目：94. 城市間貨物運輸 I (kamacoder.com)

思路：

Bellman_ford 算法 每次都是對所有邊進行松弛，其實是多做了一些無用功。

只需要對 上一次松弛的時候更新過的節點作為出發節點所連接的邊 進行松弛就夠了。

因此，關鍵在于記錄上次松弛更新過的節點，用隊列來記錄。

答案

import java.util.*;class Edge {int to;  // 鏈接的節點int val; // 邊的權重Edge(int t, int w) {to = t;val = w;}
}public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();  // 頂點數int m = scanner.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 p1 = scanner.nextInt();int p2 = scanner.nextInt();int val = scanner.nextInt();// p1 指向 p2，權值為 valgraph.get(p1).add(new Edge(p2, val));}int start = 1;  // 起點int end = n;    // 終點int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;Queue<Integer> queue = new LinkedList<>();queue.offer(start); // 隊列里放入起點while (!queue.isEmpty()) {int node = queue.poll();for (Edge edge : graph.get(node)) {int from = node;int to = edge.to;int value = edge.val;if (minDist[to] > minDist[from] + value) { // 開始松弛minDist[to] = minDist[from] + value;queue.offer(to);}}}if (minDist[end] == Integer.MAX_VALUE) {System.out.println("unconnected"); // 不能到達終點} else {System.out.println(minDist[end]); // 到達終點最短路徑}scanner.close();}
}

小結

鄰接表存儲，方便找到?上一次松弛時，更新過的節點作為出發節點所連接的邊

List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());
}

?使用LinkedList實現Queue，不斷從中 poll 出節點node，操作?node?的?edge，將 node.to 加入到隊列中

Queue<Integer> queue = new LinkedList<>();
queue.offer(start); // 隊列里放入起點while (!queue.isEmpty()) {int node = queue.poll();for (Edge edge : graph.get(node)) {int from = node;int to = edge.to;int value = edge.val;if (minDist[to] > minDist[from] + value) { // 開始松弛minDist[to] = minDist[from] + value;queue.offer(to);}}
}

95.城市間貨物運輸|| （Bellman_ford判斷負權回路）

題目：95. 城市間貨物運輸 II (kamacoder.com)

思路：出現負權回路，按照之前的思路，會一直循環回路，使得成本不斷減小，因此核心思路是，在Bellman_ford標準版基礎上，再松弛一次，看結果是否變化

SPFA(Bellman_ford優化版)，則是看節點加入隊列次數是否超過n-1次

答案

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();  // 頂點數int m = scanner.nextInt();  // 邊數List<int[]> edges = new ArrayList<>();// 將所有邊保存起來for (int i = 0; i < m; i++) {int p1 = scanner.nextInt();int p2 = scanner.nextInt();int val = scanner.nextInt();edges.add(new int[]{p1, p2, val});}int start = 1;  // 起點int end = n;    // 終點int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;boolean flag = false;// 對所有邊松弛 n 次，最后一次判斷負權回路for (int i = 1; i <= n; i++) {for (int[] edge : edges) {int from = edge[0];int to = edge[1];int price = edge[2];if (i < n) {if (minDist[from] != Integer.MAX_VALUE && minDist[to] > minDist[from] + price) {minDist[to] = minDist[from] + price;}} else { // 多加一次松弛判斷負權回路if (minDist[from] != Integer.MAX_VALUE && minDist[to] > minDist[from] + price) {flag = true;}}}}if (flag) {System.out.println("circle");} else if (minDist[end] == Integer.MAX_VALUE) {System.out.println("unconnected");} else {System.out.println(minDist[end]);}scanner.close();}
}

95.城市間貨物運輸|||（Bellman_ford單源有限最短路徑）

題目：96. 城市間貨物運輸 III (kamacoder.com)

思路：關鍵是在于，每次松弛要基于上一次松弛的結果

答案

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();  // 頂點數int m = scanner.nextInt();  // 邊數List<int[]> edges = new ArrayList<>();// 將所有邊保存起來for (int i = 0; i < m; i++) {int p1 = scanner.nextInt();int p2 = scanner.nextInt();int val = scanner.nextInt();edges.add(new int[]{p1, p2, val});}int src = scanner.nextInt();  // 起點int dst = scanner.nextInt();  // 終點int k = scanner.nextInt();    // 最大邊數int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[src] = 0;int[] minDistCopy = new int[n + 1];// 進行 k+1 次松弛操作for (int i = 1; i <= k + 1; i++) {System.arraycopy(minDist, 0, minDistCopy, 0, minDist.length); // 獲取上一次計算的結果for (int[] edge : edges) {int from = edge[0];int to = edge[1];int price = edge[2];// 注意使用 minDistCopy 來計算 minDistif (minDistCopy[from] != Integer.MAX_VALUE && minDist[to] > minDistCopy[from] + price) {minDist[to] = minDistCopy[from] + price;}}}if (minDist[dst] == Integer.MAX_VALUE) {System.out.println("unreachable"); // 不能到達終點} else {System.out.println(minDist[dst]); // 到達終點最短路徑}scanner.close();}
}

小結

更新用的是minDist，判斷用的是minDistCopy

if (minDistCopy[from] != Integer.MAX_VALUE && minDist[to] > minDistCopy[from] + price) {minDist[to] = minDistCopy[from] + price;
}