概述
最短路径 属于图论用语，它旨在求解图中任意两点间的最短距离。
我们在此介绍四种最短路径搜索算法 —— Dijkstra 算法、Floyd 算法、Bellman-Ford 算法及 SPFA 算法。
Dijkstra 算法
Dijkstra 算法用于求取单源最短路径，它仅适用于无负权边场景。
该算法思想与 Prim 算法基本一致，均是基于贪心思想。其步骤描述如下 (假定图中节点集合为 $V$)：
- 选定图中某一节点指定为单源，记为 $root$。
- 构建两个集合 $S$ 和 $T$ ($S$ 表示节点集合中已求得最短路径的节点集，$T$ 表示节点集合中未求得最短路径的节点集)，并初始化它们为 $S = {root}, T = V - {root}$。
- 选择 $T$ 中距离 $root$ 节点最近的节点，将其从 $T$ 中删去并将其加入至 $S$ 中，根据此节点更新 $T$ 中其余节点到 $root$ 节点的距离信息。
- 循环迭代步骤 3，直至 $S == V$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| public int[][] dijkstra(int[][] graph) {
int[] distance = new int[graph.length];
int[][] paths = new int[graph.length][graph[0].length];
for (int i = 0; i < graph.length; i++) {
distance[i] = graph[0][i];
Arrays.fill(paths[i], INF);
if (distance[i] != INF) {
paths[i][0] = 0;
paths[i][1] = i;
}
}
distance[0] = 0;
paths[0][0] = 0;
for (int i = 0; i < graph.length - 1; i++) {
int minIndex = 0;
int minDistance = INF;
for (int j = 0; j < graph.length; j++) {
if (distance[j] > 0 && distance[j] < minDistance) {
minIndex = j;
minDistance = distance[j];
}
}
distance[minIndex] = -distance[minIndex];
for (int j = 0; j < graph.length; j++) {
if (distance[j] > 0 && minDistance + graph[minIndex][j] < distance[j]) {
distance[j] = minDistance + graph[minIndex][j];
Arrays.fill(paths[j], INF);
for (int s = 0; s < paths[minIndex].length; s++) {
paths[j][s] = paths[minIndex][s];
if (paths[j][s] == INF) {
paths[j][s] = j;
break;
}
}
}
}
}
return paths;
}
|
Floyd 算法
Floyd 算法用于求取全局最短路径，它适用于有无负权边场景，但是不适用于负环回路场景，它基于动态规划而实现。
从任意节点 $i$ 到任意节点 $j$ 的最短路径不外乎两种情况：从 $i$ 直接到达 $j$ 、从 $i$ 出发借助于中间节点 $k$ 到达 $j$。基于此我们可构建状态 $f[k][i][j]$，它表示借助于前 $k$ 个节点作为中间节点所构建 $i$ 到 $j$ 的最短路径值。那么容易得到状态方程：
$$f[k][i][j] = min(f[k - 1][i][j], f[k - 1][i][k], f[k - 1][k][j])$$
初始状态即为 $f[0][i][j] = edge[i][j]$ ($edge[i][j]$ 表示边权重)，循环迭代处理至 $f[V.size()][i][j]$ ($V$ 表示图顶点集) 便得到全局最短路径。
观察该状态转换方程，我们可以发现：当前状态 $f[k][][]$ 仅依赖于 $f[k - 1][][]$，故而使用两个矩阵迭代更新即可完成循环迭代过程。
更进一步，我们发现：$f[k - 1][i][k] == f[k][i][k] 且 f[k - 1][k][j] == f[k][k][j]$，此时我们可直接在当前矩阵中完成更新操作 (非常神奇地观察)。
此时可以给出 Floyd 算法，十分地简洁：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public int[][] floyd(int[][] graph) {
int[][] D = new int[graph.length][graph[0].length];
int[][] P = new int[graph.length][graph[0].length];
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph[0].length; j++) {
D[i][j] = graph[i][j];
P[i][j] = j;
}
}
for (int k = 0; k < graph.length; k++) {
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph[0].length; j++) {
if (D[i][k] + D[k][j] < D[i][j]) {
D[i][j] = D[i][k] + D[k][j];
P[i][j] = P[i][k];
}
}
}
}
return P;
}
|
Bellman-Ford 算法
Bellman-Ford 算法用于求取单源最短路径，它适用于有无负权边场景，同时可判断是否存在负环回路。
Bellman-Ford 算法步骤描述如下 (假定图中节点集合为 $V$)：
- 选定图中某一节点指定为单源，记为 $root$。
- 初始化所有节点到 $root$ 的最短路径值，记为 $distance[i]$。
- 对图中所有边尝试执行松弛操作，即对于边 $edge[i][j]$ 而言，如果 $distance[i] + edge[i][j] < distance[j]$，则更新 $distance[j] = distance[i] + edge[i][j]$。
- 循环迭代步骤 3 $V.size() - 1$ 次即可得到结果。
重点解释：为什么循环迭代 $V.size() - 1$ 次可以得到单源最短路径结果？
松弛操作具有一个性质：如果 $p = (v_0,v_1,\dots,v_k)$ 是从源点 $v_0$ 到终点 $v_k$ 的最短路径，并且我们执行松弛操作的顺序为 $edge[v_0][v_1],\dots,edge[v_{k-1},v_k]$，那么这些松弛操作完成后得到的 $distance[v_k]$ 必定是源点 $v_0$ 到终点 $v_k$ 的最短路径值。并且该性质成立条件与其他松弛操作无关，即可在这些松弛操作中穿插其他松弛操作，只要保证这些松弛操作按序执行即可。
该性质比较容易理解，故而我们不予证明 (好吧，就是不会 😅)。由于组成单源最短路径的边数不可能超过 $V.size() - 1$，根据松弛操作性质，我们可在 $V.size() - 1$ 次内得到单源最短路径。如果我们再次循环一次，此时如果存在松弛操作被执行，便可判断图中存在负环回路。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| public int[][] bellmanFord(int[][] graph) {
int[] distance = new int[graph.length];
int[][] paths = new int[graph.length][graph[0].length];
Arrays.fill(distance, INF);
distance[0] = 0;
for (int i = 0; i < graph.length; i++) {
Arrays.fill(paths[i], INF);
}
paths[0][0] = 0;
for (int k = 1; k < graph.length; k++) {
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph[0].length; j++) {
if (graph[i][j] != INF && distance[i] + graph[i][j] < distance[j]) {
distance[j] = distance[i] + graph[i][j];
Arrays.fill(paths[j], INF);
for (int s = 0; s < paths[i].length; s++) {
paths[j][s] = paths[i][s];
if (paths[j][s] == INF) {
paths[j][s] = j;
break;
}
}
}
}
}
}
return paths;
}
|
SPFA 算法
SPFA 算法是 Bellman-Ford 算法的优化版本，其优化点在于：针对需要进行松弛操作的边执行松弛操作。
在 Bellman-Ford 算法中，直接对图中所有边尝试执行松弛操作，然而并非所有的边都是需要进行松弛操作的。如果可以避免无效的尝试松弛操作，那么就可以进一步降低算法的时间复杂度。
第一轮执行 Bellman-Ford 算法时，我们将会发现只有以单源为出发点的那些边才是真正需要进行松弛操作的，其余边的松弛操作尝试均是没有必要地，并且记基于松弛操作更新最短路径信息的点集为 $v$；第二轮执行 Bellman-Ford 算法时，我们又会发现只有以 $v$ 中点为出发点的那些边才是真正需要进行松弛操作的，其余边的松弛操作尝试均是没有必要地，以此类推，均是如此规律。
基于此规律，我们可将待松弛点依次放入队列之中，按序松弛点对应边。当队列为空时，松弛操作完成并且最短路径求取完成，这基本上是 SPFA 算法的核心要义。
在 SPFA 算法中，如果需要判断图中是否存在负环回路，只要判断特定待松弛点进入队列次数是否超过 $V.size() - 1$ 次即可。
在代码实现中，如果待松弛点已经入队，则无需再次入队。如此操作的原因在于：即使不将该点再次放入队列之中，已放入队列的该点它会完成所需的松弛操作，将其再次放入队列之中完全是没有必要的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| public int[][] spfa(int[][] graph) {
int[] distance = new int[graph.length];
int[][] paths = new int[graph.length][graph[0].length];
ArrayDeque<Integer> queue = new ArrayDeque<>();
boolean[] in = new boolean[graph.length];
Arrays.fill(distance, INF);
for (int i = 0; i < graph.length; i++) {
Arrays.fill(paths[i], INF);
}
Arrays.fill(in, false);
distance[0] = 0;
paths[0][0] = 0;
in[0] = true;
queue.push(0);
while (!queue.isEmpty()) {
Integer index = queue.pop();
for (int i = 0; i < graph[0].length; i++) {
if (graph[index][i] != INF && distance[index] + graph[index][i] < distance[i]) {
distance[i] = distance[index] + graph[index][i];
Arrays.fill(paths[i], INF);
for (int s = 0; s < paths[index].length; s++) {
paths[i][s] = paths[index][s];
if (paths[i][s] == INF) {
paths[i][s] = i;
break;
}
}
if (in[i] == false) {
queue.push(i);
}
}
}
}
return paths;
}
|