算法模板（Java版）_图的最短路径

@ZZHow(ZZHow1024)

图的最短路径问题：

• 单源最短路
  • 所有边权都是正数
    • 朴素 Dijkstra 算法 $O(n^2)$
    • 堆优化版 Dijkstra 算法 $O(m\ast lo{g}_{2}n)$
  • 存在负权边
    • Bellman-Ford 算法 $O(n\ast m)$
    • SPFA 算法 $一般O(m)，最坏O(n\ast m)$
• 多源汇最短路
  • Floyd 算法 $O(n^3)$

朴素 Dijkstra

迪杰斯特拉算法采用的是一种贪心的策略。进行 n 次迭代去确定每个点到起点的最小值，最后输出的终点的即为我们要找的最短路的距离。

• 例题：AcWing 849. Dijkstra求最短路 I

import java.util.Scanner;public class Main {static final int N = 510;static long[][] g = new long[N][N];static long[] dist = new long[N];static boolean[] st = new boolean[N];public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();for (int i = 0; i <= n; i++)for (int j = 0; j <= n; j++)g[i][j] = Integer.MAX_VALUE;while (m-- != 0) {int a = scanner.nextInt();int b = scanner.nextInt();int c = scanner.nextInt();g[a][b] = Math.min(g[a][b], c);}System.out.println(dijkstra(n));}public static long dijkstra(int n) {for (int i = 0; i <= n; i++)dist[i] = Integer.MAX_VALUE;dist[1] = 0;for (int i = 0; i < n; i++) {int t = -1;for (int j = 1; j <= n; j++)if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;st[t] = true;for (int j = 1; j <= n; j++)dist[j] = Math.min(dist[j], dist[t] + g[t][j]);}if (dist[n] == Integer.MAX_VALUE)return -1;elsereturn dist[n];}
}

堆优化版 Dijkstra

对朴素版 Dijkstra 进行优化，在时间复杂度最高的寻找距离最短的点 $O(n^2)$ 时可以使用小根堆优化，Java 语言可使用优先队列(PriorityQueue)，配合自定义的 Pair 类实现。

• 例题：AcWing 850. Dijkstra求最短路 II

import java.util.*;public class Main {static final int N = 1000010;static int idx = 0;static int[] h = new int[N];static int[] e = new int[N];static int[] w = new int[N];static int[] ne = new int[N];static long[] dist = new long[N];static boolean[] st = new boolean[N];public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();Arrays.fill(h, -1);while (m-- != 0) {int a = scanner.nextInt();int b = scanner.nextInt();int c = scanner.nextInt();add(a, b, c);}System.out.println(dijkstra(n));}public static void add(int a, int b, int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;}public static long dijkstra(int n) {Arrays.fill(dist, Integer.MAX_VALUE);dist[1] = 0;Queue<Pair> heap = new PriorityQueue<>();heap.add(new Pair(0L, 1));while (!heap.isEmpty()) {Pair t = heap.poll();long distance = t.first;int ver = t.second;if (st[ver])continue;st[ver] = true;for (int i = h[ver]; i != -1; i = ne[i]) {int j = e[i];if (dist[j] > distance + w[i]) {dist[j] = distance + w[i];heap.add(new Pair(dist[j], j));}}}if (dist[n] == Integer.MAX_VALUE)return -1;elsereturn dist[n];}
}class Pair implements Comparable<Pair> {public long first;public int second;public Pair() {}public Pair(long a, int b) {this.first = a;this.second = b;}@Overridepublic int compareTo(Pair o) {return (int)Math.signum(this.first - o.first);}
}

bellman-ford

迭代 $n$ 次，每次循环所有边$(a,b,w)$，更新路径：dist[b] = min(dist[b], dist[a] + w);（松弛操作）。全部操作完后满足三角不等式：$dist[b]\le dist[a]+w$

• 例题：AcWing 853. 有边数限制的最短路

import java.util.*;public class Main {public static int n;public static int m;public static int k;public static int[] dist;public static int[] backup;public static Edge[] edge;public static final int MAX = 0x3f3f3f3f;public static void main(String[] args) {Scanner scanner= new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();k = scanner.nextInt();dist = new int[n + 10];Arrays.fill(dist, MAX);dist[1] = 0;edge = new Edge[m + 10];for (int i = 0; i < m; i++) {int a = scanner.nextInt();int b = scanner.nextInt();int w = scanner.nextInt();edge[i] = new Edge(a, b, w);}int t = bellmanFord();if (t > MAX >> 1)System.out.println("impossible");elseSystem.out.println(t);}public static int bellmanFord() {for (int i = 0; i < k; i++) {backup = Arrays.copyOf(dist, dist.length);for (int j = 0; j < m; j++) {int a = edge[j].a;int b = edge[j].b;int w = edge[j].w;dist[b] = Math.min(dist[b], backup[a] + w);}}return dist[n];}
}class Edge {public int a;public int b;public int w;public Edge(int a, int b, int w) {this.a = a;this.b = b;this.w = w;}
}

SPFA

针对 bellman-ford 算法的 dist[b] = Math.min(dist[b], backup[a] + w); 使用队列进行优化。

• 例题：AcWing 851. spfa求最短路
• 例题：AcWing 852. spfa判断负环

import java.util.*;public class Main {public static int n;public static int m;public static int[] h;public static int[] w;public static int[] e;public static int[] ne;public static int idx;public static int[] dist;public static boolean[] st;public static final int MAX = 0x3f3f3f3f;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();h = new int[n + 10];w = new int[m + 10];e = new int[m + 10];ne = new int[m + 10];dist = new int[n + 10];st = new boolean[n + 10];Arrays.fill(h, -1);while (m-- != 0) {int a = scanner.nextInt();int b = scanner.nextInt();int c = scanner.nextInt();add(a, b, c);}int t = spfa();if (t > MAX >> 1)System.out.println("impossible");elseSystem.out.println(t);}public static void add(int a, int b, int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;}public static int spfa() {Arrays.fill(dist, MAX);dist[1] = 0;Queue<Integer> q = new ArrayDeque<>();q.add(1);st[1] = true;while (!q.isEmpty()) {int t = q.poll();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (dist[j] > dist[t] + w[i]) {dist[j] = dist[t] + w[i];if (!st[j]) {q.add(j);st[j] = true;}}}}return dist[n];}
}

Floyd

基于动态规划。枚举 $k,i,j$ 更新路径：d(i, j) = min(d(i, j), d(i, k) + d(k, j));

• 例题：AcWing 854. Floyd求最短路

import java.util.*;public class Main {public static int n;public static int m;public static int k;public static int[][] d;public static final int MAX = 0x3f3f3f3f;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();k = scanner.nextInt();d = new int[n + 10][n + 10];for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (i == j)d[i][j] = 0;elsed[i][j] = MAX;while (m-- != 0) {int a = scanner.nextInt();int b = scanner.nextInt();int w = scanner.nextInt();d[a][b] = Math.min(d[a][b], w);}floyd();while (k-- != 0) {int a = scanner.nextInt();int b = scanner.nextInt();if (d[a][b] > MAX >> 1)System.out.println("impossible");elseSystem.out.println(d[a][b]);}}public static void floyd() {for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);}
}