一圖勝千言

單源最短路徑

正權值 樸素Dijkstra

dijkstra算法思想是維護一個永久集合U，全部點集合V。

循環n -1次

從源點開始，在未被訪問的節點中，選擇距離源點最近的節點 t。

以節點 t 為中間節點，更新從起點到其他節點的最短距離。對于每個節點 j，比較當前的 distance[j] 和 distance[t] + graph[t][j]，取較小值作為新的 distance[j]。

將節點 t 標記為已訪問。

【例題】

給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為正值。

請你求出 1 號點到 n 號點的最短距離，如果無法從 1 號點走到 n 號點，則輸出 ?1。

輸入格式

第一行包含整數 n 和 m。

接下來 m 行每行包含三個整數 x,y,z，表示存在一條從點 x 到點 y 的有向邊，邊長為 z。

輸出格式

輸出一個整數，表示 1 號點到 n 號點的最短距離。

如果路徑不存在，則輸出 ?1。

數據范圍

1≤n≤500,
1≤m≤$10^5$,
圖中涉及邊長均不超過10000。

輸入樣例：

3 3
1 2 2
2 3 1
1 3 4

輸出樣例：

3

import java.io.*;
import java.util.*;
public class Main {static final int MAX_NUM = 2147483647 / 2;static final int N = 510;static final int M = 100010;static int[][] graph = new int[N][N];static int[] used = new int[N];static int[] distance = new int[N];static int n, m;public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String row1 = br.readLine();String[] items = row1.split(" ");n = Integer.parseInt(items[0]);m = Integer.parseInt(items[1]);//初始化將graph全初始化為無窮大for(int i = 0; i <= n; i++) {for(int j = 0; j <= n; j++) {graph[i][j] = MAX_NUM;}}//存儲鄰接矩陣while(m-- > 0) {String row = br.readLine();String[] data = row.split(" ");int x = Integer.parseInt(data[0]);int y = Integer.parseInt(data[1]);int z = Integer.parseInt(data[2]);//因為可能會有重邊，只保存最小的graph[x][y] = Math.min(graph[x][y], z);}System.out.print(dijkstra());br.close();}public static int dijkstra() {//將距離初始化為最大值for(int i = 0; i <= n; i++) {distance[i] = MAX_NUM;}distance[1] = 0;for(int i = 0; i < n - 1; i++) {int t = -1;//尋找與永久集合中權值最小的結點for(int j = 1; j <= n; j++) {if(used[j] == 0 && (t == -1 || distance[t] > distance[j])) {t = j;}}//根據t計算從初結點到后序結點和從t結點到后序結點那個值更小for(int j = 1; j <= n; j++) {distance[j] = Math.min(distance[j], distance[t] + graph[t][j]);}//標記t為用過結點used[t] = 1;}if(distance[n] == MAX_NUM) {return -1;} else {return distance[n];}}
}

正權值 堆優化Dijkstra

堆優化版通過優先隊列（堆）來快速找到距離源點最近的節點，每次從堆中取出最小元素的時間復雜度為 (O(\log n))，而遍歷所有邊的時間復雜度為 (O(m))。

樸素版 Dijkstra：適用于稠密圖，即邊的數量接近節點數量的平方的情況。因為在稠密圖中，鄰接矩陣可以更方便地存儲和訪問圖的信息。

堆優化版 Dijkstra：適用于稀疏圖，即邊的數量遠小于節點數量的平方的情況。在稀疏圖中，鄰接表可以節省存儲空間，而優先隊列可以提高尋找最小距離節點的效率。

核心步驟

當堆不為空時，從堆中取出距離源點最近的節點 no 及其距離 d。

如果節點 no 已經確定最短路徑，則跳過該節點。

標記節點 no 已經確定最短路徑。

遍歷節點 no 的所有鄰接節點 j，如果通過節點 no 到達節點 j 的距離比當前記錄的距離更短，則更新 distance[j] 的值，并將節點 j 及其新的距離加入堆中。

【例題】

給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為非負值。

請你求出 1 號點到 n 號點的最短距離，如果無法從 1 號點走到 n 號點，則輸出?1。

輸入格式

第一行包含整數 n 和 m。

接下來 m 行每行包含三個整數 x,y,z，表示存在一條從點 x 到點 y 的有向邊，邊長為 z。

輸出格式

輸出一個整數，表示 1 號點到 n 號點的最短距離。

如果路徑不存在，則輸出 ?1。

數據范圍

1≤n,m≤1.5×$10^5$,
圖中涉及邊長均不小于 0，且不超過 10000。
數據保證：如果最短路存在，則最短路的長度不超過 $10^9$。

輸入樣例：

3 3
1 2 2
2 3 1
1 3 4

輸出樣例：

3

import java.io.*;
import java.util.*;
public class Main {static final int N = 100010;static final int MAX_NUM = 2147483647 / 2;static int[] head = new int[N];static int[] value = new int[N];static int[] weight = new int[N];static int[] ne = new int[N];static int[] used = new int[N];static int[] distance = new int[N];static int n, m, idx;public static void main(String[] args) throws Exception{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] items = br.readLine().split(" ");n = Integer.parseInt(items[0]);m = Integer.parseInt(items[1]);//初始化head數組Arrays.fill(head, -1);//讀取m次數據while(m-- > 0) {String[] data = br.readLine().split(" ");int x = Integer.parseInt(data[0]);int y = Integer.parseInt(data[1]);int z = Integer.parseInt(data[2]);add(x, y, z);}System.out.print(dijkstra());}static void add(int from, int to, int w) {value[idx] = to;weight[idx] = w;ne[idx] = head[from];head[from] = idx++;}static int dijkstra() {//初始化距離Arrays.fill(distance, MAX_NUM);distance[1] = 0;PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);heap.offer(new int[]{0, 1});while(!heap.isEmpty()) {//從堆中取出離源點距離最小的元素int[] item = heap.poll();int d = item[0];int no = item[1];//判斷該點是否已經在永久集合中if(used[no] == 1) {continue;}used[no] = 1;//根據這一點去計算其他通過該點達到的結點的距離是否更新for(int i = head[no]; i != -1; i = ne[i]) {//結點編號int j = value[i];if(distance[j] > distance[no] + weight[i]) {distance[j] = distance[no] + weight[i];heap.offer(new int[]{distance[j], j});}}}return distance[n] == MAX_NUM ? -1 : distance[n];}
}

負權值 bellman-ford

核心邏輯

初始化

• 將 distance 數組的所有元素初始化為無窮大 MAX_NUM，表示初始時所有節點到源點的距離都是未知的。
• 將源點（節點 1）的距離 distance[1] 初始化為 0，因為源點到自身的距離為 0。

迭代更新距離

• 進行 k 次迭代，每次迭代的目的是保證找到的最短路徑最多經過 k 條邊。
• 在每次迭代之前，先將 distance 數組復制到 temp 數組中。這一步是為了避免在更新距離時出現數據串聯的問題，確保每次更新都是基于上一次迭代的結果。
• 遍歷 edges 列表中的每一條邊 e，對于每條邊，嘗試通過這條邊來更新終點 e.to 的最短距離。具體來說，比較當前 distance[e.to] 和 temp[e.from] + e.weight 的大小，取較小值作為新的 distance[e.to]。（對每一條邊進行松弛操作）

如果經歷至多n - 1次迭代，能夠收斂于穩定，否則一定會有負環

負環每走一次都會使得距離變短，導致無窮循環

對于由n個結點構成的鏈路，最多有n-1跳，所以超過n - 1跳就一定會有負環存在，且不可能是最短路徑

【例題】

給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數。

請你求出從 1 號點到 n 號點的最多經過 k 條邊的最短距離，如果無法從 1 號點走到 n 號點，輸出 impossible。

注意：圖中可能 存在負權回路 。

輸入格式

第一行包含三個整數 n,m,k。

接下來 mm 行，每行包含三個整數 x,y,z，表示存在一條從點 x 到點 y 的有向邊，邊長為 z。

點的編號為 1～n。

輸出格式

輸出一個整數，表示從 1 號點到 n 號點的最多經過 k 條邊的最短距離。

如果不存在滿足條件的路徑，則輸出 impossible。

數據范圍

1≤n,k≤500,
1≤m≤10000,
1≤x,y≤n，
任意邊長的絕對值不超過 10000。

輸入樣例：

3 3 1
1 2 1
2 3 1
1 3 3

輸出樣例：

3

import java.io.*;
import java.util.*;
public class Main {static class edge {public int from;public int to;public int weight;public edge(int from, int to, int weight) {this.from = from;this.to = to;this.weight = weight;}}static final int N = 510;static final int MAX_NUM = 2147483647 / 2;static int n, m, k;static List<edge> edges = new ArrayList<>();static int[] distance = new int[N];public static void main(String[] args) throws Exception{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] items = br.readLine().split(" ");n = Integer.parseInt(items[0]);m = Integer.parseInt(items[1]);k = Integer.parseInt(items[2]);while (m-- > 0) {String[] data = br.readLine().split(" ");int from = Integer.parseInt(data[0]);int to = Integer.parseInt(data[1]);int weight = Integer.parseInt(data[2]);edges.add(new edge(from, to, weight));}//調用bellman ford算法bellmanFord();}public static void bellmanFord() {//初始化distanceArrays.fill(distance, MAX_NUM);distance[1] = 0;//k次循環保證最多經過k條邊的距離for (int i = 0; i < k; i++) {//拷貝distance數組，避免數據串聯int[] temp = Arrays.copyOf(distance, distance.length);for (edge e : edges) {distance[e.to] = Math.min(distance[e.to], temp[e.from] + e.weight );}}//判斷distance[n]的大小, MAX_NUM / 2 是終點前的負值邊對對distance[n]產生影響，會使最大值減少 k * weight if (distance[n] > MAX_NUM / 2) {System.out.println("impossible");} else {System.out.println(distance[n]);}}
}

負權值 SPFA

Bellman - Ford 算法的時間復雜度是 (O(k m))，其中 k 通常是節點數 n，也就是在一般情況下時間復雜度為 (O(n m))。這是因為在每一輪迭代中，它都會對圖中的每一條邊進行松弛操作，不管這條邊是否能真正更新節點的最短距離。在很多情況下，大量的松弛操作是不必要的，導致算法效率較低。

當圖的規模較大時，Bellman - Ford 算法的性能會變得很差。而 SPFA（Shortest Path Faster Algorithm）算法就是為了優化 Bellman - Ford 算法的效率而提出的，它通過隊列來減少不必要的松弛操作，從而在很多情況下能顯著提高算法的執行效率。

SPFA 算法的核心思想是利用隊列來維護待處理的節點。只有當一個節點的最短距離被更新時，才將其加入隊列，等待后續對其出邊進行松弛操作。這樣就避免了 Bellman - Ford 算法中對所有邊進行無意義的松弛操作，從而減少了不必要的計算。

初始化

• 定義常量 N 表示節點的最大數量，MAX_NUM 表示無窮大。
• 初始化鄰接表相關數組 head、value、weight、ne 用于存儲圖的信息。
• 初始化隊列 queue，隊頭指針 hh 和隊尾指針 tt。
• 初始化 distance 數組，將所有節點的距離初始化為無窮大，源點（節點 1）的距離初始化為 0。
• 初始化 inQueue 數組，用于標記節點是否在隊列中，初始時所有節點都不在隊列中。

入隊操作

將源點（節點 1）加入隊列，并標記其在隊列中。

隊列處理

• 當隊列不為空時，從隊頭取出一個節點 t，并標記該節點不在隊列中。

• 遍歷節點t的所有出邊：

  • 對于每一條出邊 (t, j)，如果通過節點 t 到達節點 j 的距離比當前記錄的 distance[j] 更短，則更新 distance[j] 的值。
  • 如果節點 j 不在隊列中，則將其加入隊列，并標記其在隊列中。

【例題】

給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數。

請你求出 1 號點到 n 號點的最短距離，如果無法從 1 號點走到 n 號點，則輸出 impossible。

數據保證不存在負權回路。

輸入格式

第一行包含整數 n 和 m。

接下來 m 行每行包含三個整數 x,y,z，表示存在一條從點 x 到點 y 的有向邊，邊長為 z。

輸出格式

輸出一個整數，表示 1 號點到 n 號點的最短距離。

如果路徑不存在，則輸出 impossible。

數據范圍

1≤n,m≤$10^5$,
圖中涉及邊長絕對值均不超過 10000。

輸入樣例：

3 3
1 2 5
2 3 -3
1 3 4

輸出樣例：

2

import java.io.*;
import java.util.*;
public class Main {static final int N = 100010;static final int MAX_NUM = 2147483647 / 2;static int[] head = new int[N];static int[] value = new int[N];static int[] weight = new int[N];static int[] ne = new int[N];static int hh = 0, tt = -1, idx = 0, n, m;static int[] queue = new int[N];static int[] distance = new int[N];static boolean[] inQueue = new boolean[N];public static void main(String[] args) throws Exception{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] row1 = br.readLine().split(" ");n = Integer.parseInt(row1[0]);m = Integer.parseInt(row1[1]);//初始化head數組Arrays.fill(head, -1);//m次讀入while(m-- > 0) {String[] data = br.readLine().split(" ");int x = Integer.parseInt(data[0]);int y = Integer.parseInt(data[1]);int z = Integer.parseInt(data[2]);add(x, y, z);}spfa();br.close();}static void add(int from, int to, int w) {value[idx] = to;weight[idx] = w;ne[idx] = head[from];head[from] = idx++;}static void spfa() {//初始化distance數組Arrays.fill(distance, MAX_NUM);distance[1] = 0;//將第一個數加入隊列queue[++tt] = 1;//更新1的狀態inQueue[1] = true;while(hh <= tt) {//從隊頭取出一個數int t = queue[hh++];//更新隊頭元素的狀態inQueue[t] = false;//遍歷該結點的所有出邊for(int i = head[t]; i != -1; i = ne[i]) {int j = value[i];if(distance[j] > distance[t] + weight[i]) {distance[j] = distance[t] + weight[i];if(inQueue[j] == false) {queue[++tt] = j;inQueue[j] = true;}}}}if(distance[n] == MAX_NUM) {System.out.print("impossible");} else {System.out.print(distance[n]);}}
}

多源最短路徑

Floyd

算法原理

Floyd 算法通過一個三層循環來逐步更新圖中各頂點對之間的最短路徑。設圖中有 n 個頂點，用鄰接矩陣 (graph[i][j]) 表示頂點 i 到頂點 j 的邊權（若 i 和 j 之間沒有邊，則權值為無窮大）。

定義一個三維數組 (dist[k][i][j]) 表示從頂點 i 到頂點 j 經過編號不超過 k 的頂點的最短路徑長度（也可簡化為二維數組 (dist[i][j]) ，在每次迭代中直接更新）。

迭代過程分析

• 初始狀態：在算法開始時，(dist[0][i][j]=graph[i][j]) ，即不經過任何中間頂點時，頂點 i 到頂點 j 的距離就是它們之間的邊權。這是符合實際情況的，因為沒有中間節點參與時，兩點間距離就是直接相連的邊權（若不相連則為無窮大）。
• 第 k 次迭代：在第 k 次迭代中，對于每一對頂點 ((i, j)) ，考慮是否經過頂點 k 會使 i 到 j 的路徑更短。即比較 (dist[k - 1][i][j]) （不經過頂點 k 時 i 到 j 的最短路徑）和 (dist[k - 1][i][k]+dist[k - 1][k][j]) （經過頂點 k ，從 i 到 k 再從 k 到 j 的路徑長度 ）的大小。取較小值作為 (dist[k][i][j]) 。

這種比較是合理的，因為如果存在一條從 i 到 j 經過頂點 k 的更短路徑，那么必然是由從 i 到 k 的最短路徑和從 k 到 j 的最短路徑組成。而在第 k 次迭代時，我們已經知道了不經過頂點 k （即經過編號小于 k 的頂點子集 ）時從 i 到 k 和從 k 到 j 的最短路徑（分別為 (dist[k - 1][i][k]) 和 (dist[k - 1][k][j]) ） 。通過這種比較和更新，我們能得到經過編號不超過 k 的頂點時 i 到 j 的最短路徑。

【例題】

給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環，邊權可能為負數。

再給定 k 個詢問，每個詢問包含兩個整數 x 和 y，表示查詢從點 x 到點 y 的最短距離，如果路徑不存在，則輸出 impossible。

數據保證圖中不存在負權回路。

輸入格式

第一行包含三個整數 n,m,k。

接下來 m 行，每行包含三個整數 x,y,z，表示存在一條從點 x 到點 y 的有向邊，邊長為 z。

接下來 k 行，每行包含兩個整數 x,y，表示詢問點 xx 到點 y 的最短距離。

輸出格式

共kk 行，每行輸出一個整數，表示詢問的結果，若詢問兩點間不存在路徑，則輸出 impossible。

數據范圍

1≤n≤200,
1≤k≤n2
1≤m≤20000,
圖中涉及邊長絕對值均不超過 10000。

輸入樣例：

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

輸出樣例：

impossible
1

import java.io.*;
import java.util.*;
public class Main {static final int MAX_NUM = 2147483647 / 2;static final int N = 210;static int n, m;static int[][] graph = new int[N][N];public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] row1 = br.readLine().split(" ");n = Integer.parseInt(row1[0]);m = Integer.parseInt(row1[1]);int q = Integer.parseInt(row1[2]);//對鄰接矩陣進行初始化for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(i == j) {graph[i][j] = 0;} else {graph[i][j] = MAX_NUM;}}}for(int i = 1; i <= m; i++) {String[] data = br.readLine().split(" ");int a = Integer.parseInt(data[0]);int b = Integer.parseInt(data[1]);int c = Integer.parseInt(data[2]);graph[a][b] = Math.min(graph[a][b], c);}floyd();//q次詢問while(q-- > 0) {String[] fromTo = br.readLine().split(" ");int from = Integer.parseInt(fromTo[0]);int to = Integer.parseInt(fromTo[1]);if(graph[from][to] > MAX_NUM / 2) {System.out.println("impossible");} else {System.out.println(graph[from][to]);}}}static void floyd() {for(int k = 1; k <= n; k++) {for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);}}}}
}