最短路
引入
在图中，求出某一点到任意一点的最短路径
单源最短路
Dijkstra
\(Dijkstra\) 是一种求解 非负权图 上单源最短路径的算法。
定义 \(S\) 为要求的单源最短路的源点
\(dis(i)\) 为 \(S\to i\) 的最短路径
松弛
在理解 \(Dijkstra\) 算法过程之前，要先理解松弛操作
我们尝试用 \(S\to u\to v\)（其中 \(S\to u\) 的路径取最短路）这条路径去更新 点 \(v\) 最短路的长度，如果这条路径更优，就进行更新。
简单来说就是选择更短的路径
对于边 \((u,v)\)，松弛操作对应下面的式子：
\[dis(v)=min(dis(v),dis(u)+w(u,v)) \]过程
将结点分成两个集合：
- 已确定最短路长度的点集（记为 \(S\) 集合）。
- 未确定最短路长度的点集（记为 \(T\) 集合）。
一开始所有的点都属于 \(T\) 集合。
初始化 \(dis(S)=0\) ，其他点的 \(dis\) 均为 \(+\infty\)。
然后重复这些操作：
- 从 \(T\) 集合中，选取一个最短路长度最小的结点，移到 \(S\) 集合中。
- 对那些刚刚被加入 \(S\) 集合的结点的所有出边执行松弛操作。
直到 \(T\) 集合为空，算法结束。
若 \(dis(i)\) 仍为\(+\infty\)，则 \(S\to i\) 不可达
时间复杂度
对于操作 \(1\) 中选取最短路长度最小的节点有多种方法
采取不同方法有着不同的时间复杂度，以下给出两种常用的方法及总时间复杂度：
- 暴力：不使用任何数据结构进行维护，每次 \(2\) 操作执行完毕后，直接在 \(T\) 集合中暴力寻找最短路长度最小的结点。\(2\) 操作总时间复杂度为 \(O(m)\)，\(1\) 操作总时间复杂度为 \(O(n^2)\)，全过程的时间复杂度为 \(O(n^2+m)=O(n^2)\)。
- 优先队列：每成功松弛一条边 \((u,v)\)，就将 \(v\) 加入优先队列中，如果同一个点的最短路被更新多次，但对于优先队列前面的元素不能删除也不能修改，只能留在队列中，因此优先队列内的元素个数是 \(O(m)\) 的，总时间复杂度为 \(O(mlog(m))\)
实现（采用邻接表存图）
\(1\) 暴力：
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
static class edge {
int v;
long w;
public edge(int v, long w) {
this.v = v;
this.w = w;
}
}
static LinkedList<edge>[] adj;
//dis[i]表示 S -> i 的最短路长度
static long[] dis;
//vis[i]判断i号节点是否被选择
static boolean[] vis;
// n个点，m条边
static int n, m;
//不要赋值为MAX，程序可能会进行加法等操作导致溢出
static final long INF = (long) 1e12;
// 求以start为源点的单源最短路
static void Dijkstra(int start) {
Arrays.fill(dis, INF);
Arrays.fill(vis, false);
//自己到自己的最短路为0
dis[start] = 0;
for (int i = 1; i <= n; ++i) {
//操作1：在未确定的集合T中选择最短路长度最小的结点
int u = 0;
long min = INF;
for (int j = 1; j <= n; ++j)
if (!vis[j] && dis[j] < min) {
u = j;
min = dis[j];
}
//如果u为初始值，则说明所有节点都被选择了
if (u == -1) return;
//将其加入集合S中
vis[u] = true;
//操作2：对加入的结点的所有出边进行松弛操作
for (edge e : adj[u])
//松弛操作
if (dis[e.v] > dis[u] + e.w)
dis[e.v] = dis[u] + e.w;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
//点的标号从1开始，即1~n
adj = new LinkedList[n + 1];
for (int i = 1; i <= n; ++i) adj[i] = new LinkedList<>();
dis = new long[n + 1];
vis = new boolean[n + 1];
// start为源点
int start = sc.nextInt();
for (int i = 0; i < m; ++i) {
int u = sc.nextInt(), v = sc.nextInt();
long w = sc.nextLong();
// 加边（有向边）
adj[u].add(new edge(v, w));
}
Dijkstra(start);
for (int i = 1; i <= n; ++i) System.out.printf("%d到%d的最短路径长度为%d\n", start, i, dis[i]);
}
}
\(2\) 优先队列：
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static class edge {
int v;
long w;
public edge(int v, long w) {
this.v = v;
this.w = w;
}
}
static LinkedList<edge>[] adj;
//dis[i]表示 S -> i 的最短路长度
static long[] dis;
//vis[i]判断i号节点是否被选择
static boolean[] vis;
// n个点，m条边
static int n, m;
//不要赋值为MAX，程序可能会进行加法等操作导致溢出
static final long INF = (long) 1e12;
// 求以start为源点的单源最短路
static void Dijkstra(int start) {
Arrays.fill(dis, INF);
Arrays.fill(vis, false);
class node {
int u;
long dis;
public node(int u, long dis) {
this.u = u;
this.dis = dis;
}
}
PriorityQueue<node> q = new PriorityQueue<>(((o1, o2) -> (int) (o1.dis - o2.dis)));
//自己到自己的最短路为0
dis[start] = 0;
q.add(new node(start, 0));
while (!q.isEmpty()) {
//操作1：选择最短路长度最小的结点
int u = q.poll().u;
//如果已经在集合中，则选择下一个节点
if (vis[u]) continue;
vis[u] = true;
//操作2：对加入的结点的所有出边进行松弛操作
for (edge e : adj[u])
//松弛操作
if (dis[e.v] > dis[u] + e.w) {
dis[e.v] = dis[u] + e.w;
q.add(new node(e.v, dis[e.v]));
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
//点的标号从1开始，即1~n
adj = new LinkedList[n + 1];
for (int i = 1; i <= n; ++i) adj[i] = new LinkedList<>();
dis = new long[n + 1];
vis = new boolean[n + 1];
// start为源点
int start = sc.nextInt();
for (int i = 0; i < m; ++i) {
int u = sc.nextInt(), v = sc.nextInt();
long w = sc.nextLong();
// 加边（有向边）
adj[u].add(new edge(v, w));
}
Dijkstra(start);
for (int i = 1; i <= n; ++i) System.out.printf("%d到%d的最短路径长度为%d\n", start, i, dis[i]);
}
}
测试数据
输入：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出：
1到1的最短路径长度为0
1到2的最短路径长度为2
1到3的最短路径长度为4
1到4的最短路径长度为3
输出路径
每次更新最短路径时，通过数组将 来结点（前驱节点）记录下来
以下给出使用优先队列的输出路径
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static class edge {
int v;
long w;
public edge(int v, long w) {
this.v = v;
this.w = w;
}
}
static LinkedList<edge>[] adj;
static long[] dis;
static boolean[] vis;
static int n, m;
static final long INF = (long) 1e12;
static int[] pre;
static void Dijkstra(int start) {
Arrays.fill(dis, INF);
Arrays.fill(vis, false);
class node {
int u;
long dis;
public node(int u, long dis) {
this.u = u;
this.dis = dis;
}
}
PriorityQueue<node> q = new PriorityQueue<>(((o1, o2) -> (int) (o1.dis - o2.dis)));
dis[start] = 0;
q.add(new node(start, 0));
while (!q.isEmpty()) {
int u = q.poll().u;
if (vis[u]) continue;
vis[u] = true;
for (edge e : adj[u])
if (dis[e.v] > dis[u] + e.w) {
dis[e.v] = dis[u] + e.w;
q.add(new node(e.v, dis[e.v]));
pre[e.v] = u;
}
}
}
static String _findPathTool(int now) {
String ans = "";
//如果还有前驱节点
if (pre[now] != 0) ans += _findPathTool(pre[now]);
ans += now + "->";
return ans;
}
static String findPath(int start, int end) {
if (start == end) return "自身到自身";
if (pre[end] == 0) return "无最短路";
return _findPathTool(pre[end]) + end;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
adj = new LinkedList[n + 1];
for (int i = 1; i <= n; ++i) adj[i] = new LinkedList<>();
dis = new long[n + 1];
vis = new boolean[n + 1];
pre = new int[n + 1];
int start = sc.nextInt();
for (int i = 0; i < m; ++i) {
int u = sc.nextInt(), v = sc.nextInt();
long w = sc.nextLong();
adj[u].add(new edge(v, w));
}
Dijkstra(start);
for (int i = 1; i <= n; ++i)
System.out.printf("%d到%d的最短路径长度为%d，最短路径为：%s\n", start, i, dis[i], findPath(start, i));
}
}
测试数据：
输入：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出：
1到1的最短路径长度为0，最短路径为：自身到自身
1到2的最短路径长度为2，最短路径为：1->2
1到3的最短路径长度为4，最短路径为：1->2->3
1到4的最短路径长度为3，最短路径为：1->2->4
例题 \(Code\)
实现 \(1\)
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
public class Main {
static class edge {
int v;
int w;
public edge(int v, int w) {
this.v = v;
this.w = w;
}
}
static LinkedList<edge>[] adj;
static int[] dis;
static boolean[] vis;
static int n, m;
static final int INF = Integer.MAX_VALUE;
static void Dijkstra(int start) {
Arrays.fill(dis, INF);
Arrays.fill(vis, false);
//自己到自己的最短路为0
dis[start] = 0;
for (int i = 1; i <= n; ++i) {
//操作1：在未确定的集合T中选择最短路长度最小的结点
int u = 0;
long min = INF;
for (int j = 1; j <= n; ++j)
if (!vis[j] && dis[j] < min) {
u = j;
min = dis[j];
}
//如果u为初始值，则说明所有节点都被选择了
if (u == -1) return;
//将其加入集合S中
vis[u] = true;
//操作2：对加入的结点的所有出边进行松弛操作
for (edge e : adj[u])
//松弛操作
if (dis[e.v] > (long) dis[u] + e.w)
dis[e.v] = dis[u] + e.w;
}
}
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(System.out);
static int get() throws IOException {
in.nextToken();
return (int) in.nval;
}
public static void main(String[] args) throws IOException {
n = get();
m = get();
//点的标号从1开始，即1~n
adj = new LinkedList[n + 1];
for (int i = 1; i <= n; ++i) adj[i] = new LinkedList<>();
dis = new int[n + 1];
vis = new boolean[n + 1];
// start为源点
int start = get();
for (int i = 0; i < m; ++i) {
int u = get(), v = get(), w = get();
// 加边（有向边）
adj[u].add(new edge(v, w));
}
Dijkstra(start);
for (int i = 1; i <= n; ++i) out.print(dis[i] + " ");
out.close();
}
}
实现 \(2\)
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
public class Main {
static class edge {
int v, w;
public edge(int v, int w) {
this.v = v;
this.w = w;
}
}
static LinkedList<edge>[] adj;
static int[] dis;
static boolean[] vis;
static int n, m;
static final int INF = Integer.MAX_VALUE;
static void Dijkstra(int start) {
Arrays.fill(dis, INF);
Arrays.fill(vis, false);
class node {
int u, dis;
public node(int u, int dis) {
this.u = u;
this.dis = dis;
}
}
PriorityQueue<node> q = new PriorityQueue<>(((o1, o2) -> o1.dis - o2.dis));
//自己到自己的最短路为0
dis[start] = 0;
q.add(new node(start, 0));
while (!q.isEmpty()) {
//操作1：选择最短路长度最小的结点
int u = q.poll().u;
//如果已经在集合中，则选择下一个节点
if (vis[u]) continue;
vis[u] = true;
//操作2：对加入的结点的所有出边进行松弛操作
for (edge e : adj[u])
//松弛操作
if (dis[e.v] > (long) dis[u] + e.w) {
dis[e.v] = dis[u] + e.w;
q.add(new node(e.v, dis[e.v]));
}
}
}
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(System.out);
static int get() throws IOException {
in.nextToken();
return (int) in.nval;
}
public static void main(String[] args) throws IOException {
n = get();
m = get();
//点的标号从1开始，即1~n
adj = new LinkedList[n + 1];
for (int i = 1; i <= n; ++i) adj[i] = new LinkedList<>();
dis = new int[n + 1];
vis = new boolean[n + 1];
// start为源点
int start = get();
for (int i = 0; i < m; ++i) {
int u = get(), v = get(), w = get();
// 加边（有向边）
adj[u].add(new edge(v, w));
}
Dijkstra(start);
for (int i = 1; i <= n; ++i) out.print(dis[i] + " ");
out.close();
}
}
全源最短路
例题：P2910 Clear And Present Danger S - 洛谷
全源最短路可以通过单源最短路求得，即对任意两个点求单源最短路。
但有更简单的方法
Floyd
forforfor 求最短路
-
是用来求任意两个结点之间的最短路的。
-
复杂度比较高，但是常数小，容易实现。
-
适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有负环）
-
是一种动态规划算法，也称插点法（每次在两个点的路径间新增点）。
过程
定义 \(dis(k,i,j)\) 表示 由 \(i\) 到 \(j\) ，且 **只允许经过节点编号为 \(1\sim k\) ** 的最短路径长度
对于 \(dis(k,i,j)\) 路径的选择分为两类：
- 路径不经过 \(k\) 点，则 \(dis(k,i,j)=dis(k-1,i,j)\)
- 路径经过 \(k\) 点，则 \(dis(k,i,j)=dis(k-1,i,k)+dis(k-1,k,j)\)
因此 \(dis(k,i,j)=min(dis(k-1,i,j),\ dis(k-1,i,k)+dis(k-1,k,j))\)
注意，当计算第 \(k\)层的 \(dis(k,i,j)\) 时，必须先将前 \(k-1\) 层的所有状态计算出来，因此循环时 \(k\) 应在最外层
初始化
- 当 \(i=j\) 时，由于自身到自身的最短路径长度为 \(0\)，则 \(dis(0,i,j)=0\)
- 当 \(i\neq j\) 且存在 \(i\to j\) 直接相连的边时，\(dis(0,i,j)=w(i,j)\)，其中 \(w(i,j)\) 为 \(i\) 到 \(j\) 的边权
- 当 \(i\neq j\) 且存在 \(i\to j\) 直接相连的边时，\(dis(0,i,j)=+\infty\)
优化
重看状态计算：
- 当路径不经过 \(k\) 点时，相当于直接将 \(k-1\) 层的值复制到 \(k\) 层
- 当路径经过 \(k\) 点时，第 \(k-1\) 层的 \(dis(k-1,i,k)\) 和 \(dis(k-1,k,j)\) 都不经过 \(k\) 点，可以直接投影到第 \(k\) 层的对应位置，即 \(dis(i,j)=dis(i,k)+dis(k,j)\)
因此，\(dis(i,j)=min(dis(i,j),\ dis(i,k)+dis(k,j))\)
性质
- 每新增一个点，就等于新增一个桥，尝试更新那些经过新桥的最短路径
- 当循环完 \(k\) 层后，会将有插点编号不超过 \(k\) 的最短路径都找出来，但是插点编号超过 \(k\) 的最短路径是找不出来的
- 当枚举完 \(n\) 层，所有的最短路径都找出来了
- 当 \(Floyd\) 算法运行后，若 \(dis(i,j)\) 为初值 \(+\infty\)，则无最短路径，即他们不可达
时间复杂度
显然，时间复杂度为 \(O(n^3)\)，空间复杂度优化前为 \(O(n^3)\)，优化后为 \(O(n^2)\)
实现
\(Floyd\) 算法不需要遍历图，因此可以选择不存图
import java.util.Scanner;
public class Main {
static int[][] dis;
static int n, m;
static final int INF = (int) 1e9;
static void Floyd() {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
//dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
if (dis[i][j] > dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
//点的标号从1开始，即1~n
dis = new int[n + 1][n + 1];
//初始化
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) dis[i][j] = dis[j][i] = INF;
dis[i][i] = 0;
}
for (int i = 0; i < m; ++i) {
//有向边
int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
dis[u][v] = w;
}
Floyd();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
if (dis[i][j] == INF) System.out.printf("%d不可达到%d\n", i, j);
else System.out.printf("%d到%d的最短路径长度为%d\n", i, j, dis[i][j]);
}
}
}
测试数据：
输入：
4 6
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出：
1到1的最短路径长度为0
1到2的最短路径长度为2
1到3的最短路径长度为4
1到4的最短路径长度为3
2不可达到1
2到2的最短路径长度为0
2到3的最短路径长度为2
2到4的最短路径长度为1
3不可达到1
3不可达到2
3到3的最短路径长度为0
3到4的最短路径长度为3
4不可达到1
4不可达到2
4不可达到3
4到4的最短路径长度为0
输出路径
每次更新最短路径时，记录插点，即记录这次结果是从哪个中转点过来的
import java.util.Scanner;
public class Main {
static int[][] dis;
static int[][] path;
static int n, m;
static final int INF = (int) 1e9;
static void Floyd() {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (dis[i][j] > dis[i][k] + dis[k][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
path[i][j] = k;
}
}
static String _findPathTool(int x, int y) {
String ans = "";
int k = path[x][y];
// 如果 x 到 k 有插点
if (path[x][k] != 0) ans += _findPathTool(x, k);
// 中转点
ans += k + "->";
// 如果 k 到 y 有插点
if (path[k][y] != 0) ans += _findPathTool(k, y);
return ans;
}
static String findPath(int x, int y) {
if (x == y) return "自身到自身";
// 如果x到y间没有插点
if (path[x][y] == 0) return x + "->" + y;
return x + "->" + _findPathTool(x, y) + y;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
//点的标号从1开始，即1~n
dis = new int[n + 1][n + 1];
path = new int[n + 1][n + 1];
//初始化
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) dis[i][j] = dis[j][i] = INF;
dis[i][i] = 0;
}
for (int i = 0; i < m; ++i) {
//有向边
int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
dis[u][v] = w;
}
Floyd();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
if (dis[i][j] == INF) System.out.printf("%d不可达到%d\n", i, j);
else System.out.printf("%d到%d的最短路径长度为%d，最短路径为：%s\n", i, j, dis[i][j], findPath(i, j));
}
}
}
测试数据：
输入：
4 6
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出：
1到1的最短路径长度为0，最短路径为：自身到自身
1到2的最短路径长度为2，最短路径为：1->2
1到3的最短路径长度为4，最短路径为：1->2->3
1到4的最短路径长度为3，最短路径为：1->2->4
2不可达到1
2到2的最短路径长度为0，最短路径为：自身到自身
2到3的最短路径长度为2，最短路径为：2->3
2到4的最短路径长度为1，最短路径为：2->4
3不可达到1
3不可达到2
3到3的最短路径长度为0，最短路径为：自身到自身
3到4的最短路径长度为3，最短路径为：3->4
4不可达到1
4不可达到2
4不可达到3
4到4的最短路径长度为0，最短路径为：自身到自身
例题 \(Code\)
import java.util.Scanner;
public class Main {
static int[][] dis;
static int[] path;
static int n, m, ans = 0;
static void Floyd() {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (dis[i][j] > dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
//点的标号从1开始，即1~n
dis = new int[n + 1][n + 1];
path = new int[m + 1];
for (int i = 1; i <= m; ++i) path[i] = sc.nextInt();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dis[i][j] = sc.nextInt();
Floyd();
for (int i = 2; i <= m; ++i) ans += dis[path[i - 1]][path[i]];
System.out.println(ans);
}
}