Content Table

图-最短路径-Floyd

使用 Floyd 算法求任一点到其他所有点 (任意两点) 之间的最短距离: 对于每个顶点 v,和任一顶点对 (i, j), i!=j, v!=i, v!=j,如果 A[i][j] > A[i][v]+A[v][j],则将 A[i][j] 更新为 A[i][v]+A[v][j] 的值,并且将 Prev[i][j] 改为 Prev[v][j]:

  • 距离表 (初始化为图的邻接矩阵)
  • 前驱表 (初始化为每点到其他任一点的前驱为自己)
  • 三层循环:
    • 第一层: 中间点 [A, B, C, D, E, F, G]
    • 第二层: 出发点 [A, B, C, D, E, F, G]
    • 第三层: 终结点 [A, B, C, D, E, F, G]
    • 出发点通过中间点到终结点的距离、出发点直连终结点的距离选最小值更新距离表: min(Lik+Lkj, Lij),同时更新前驱表

第一轮: 以 A 为中间节点,点 X 通过 A 到点 Y 的距离为 min(XA+AY, XY): BAA, BAB, BAC, BAD, BAE, BAF, BAG, CAA, CAB, …
第二轮: 以 B 为中间节点,…

第七轮: 以 G 为中间节点,…

1
2
3
4
5
6
7
8
9
10
11
12
// 核心: Floyd 算法计算任意 2 点之间的最短距离
final int len = distance.length;
for (int v = 0; v < len; v++) { // 第一层: 中间点
for (int i = 0; i < len; i++) { // 第二层: 出发点
for (int j = 0; j < len; j++) { // 第三层: 终结点
if (distance[i][v] + distance[v][j] < distance[i][j]) {
distance[i][j] = distance[i][v] + distance[v][j];
path[i][j] = path[v][j];
}
}
}
}

参考资料:

图解使用 Floyd 算法生成最短路径的过程:

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
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package graph;

import java.util.LinkedList;
import java.util.List;

public class Floyd {
private static final int N = 1000; // 表示无穷大距离

public static void main(String[] args) {
// 顶点
char[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };

// 距离表
int[][] distance = {
{ 0, 5, 7, N, N, N, 2 },
{ 5, 0, N, 9, N, N, 3 },
{ 7, N, 0, N, 8, N, N },
{ N, 9, N, 0, N, 4, N },
{ N, N, 8, N, 0, 5, 4 },
{ N, N, N, 4, 5, 0, 6 },
{ 2, 3, N, N, 4, 6, 0 },
};

// 前驱表
int[][] path = new int[7][7];
for (int i = 0; i < path.length; i++) {
for (int j = 0; j < path[0].length; j++) {
path[i][j] = i;
}
}

// 核心: Floyd 算法计算任意 2 点之间的最短距离
// 对于每个顶点 v,和任一顶点对 (i, j), i!=j, v!=i, v!=j,
// 如果 A[i][j] > A[i][v]+A[v][j],则将 A[i][j] 更新为 A[i][v]+A[v][j] 的值,并且将 Prev[i][j] 改为 Path[v][j]
final int len = distance.length;
for (int v = 0; v < len; v++) { // 第一层: 中间点
for (int i = 0; i < len; i++) { // 第二层: 出发点
for (int j = 0; j < len; j++) { // 第三层: 终结点
if (distance[i][v] + distance[v][j] < distance[i][j]) {
distance[i][j] = distance[i][v] + distance[v][j];
path[i][j] = path[v][j];
}
}
}
}

showDistance(distance, vertices);
showPath(path, vertices);

System.out.println(getPath('D', 'C', path, vertices));
}

/**
* 求 a 点到 b 点的最短路径
*/
public static List<Character> getPath(char a, char b, int[][] path, char[] vertices) {
List<Character> vs = new LinkedList<>();
int start = a - 'A';
int end = b - 'A';

while (end != start) {
vs.add(0, vertices[end]);
end = path[start][end];
}
vs.add(0, vertices[start]);

return vs;
}

// 显示距离表
private static void showDistance(int[][] distance, char[] vertices) {
final int len = distance.length;

out(' ');
for (int i = 0; i < len; i++) {
out(vertices[i]);
}
for (int i = 0; i < len; i++) {
System.out.println();
out(vertices[i]);

for (int j = 0; j < len; j++) {
out(distance[i][j]);
}
}
System.out.println();
System.out.println();
}

// 显示路径表
private static void showPath(int[][] path, char[] vertices) {
final int len = path.length;

out(' ');
for (int i = 0; i < len; i++) {
out(vertices[i]);
}
for (int i = 0; i < len; i++) {
System.out.println();
out(vertices[i]);

for (int j = 0; j < len; j++) {
out(vertices[path[i][j]]);
}
}
System.out.println();
System.out.println();
}

private static void out(int n) {
System.out.printf("%5s", (n == N) ? "N" : n);
}
private static void out(char c) {
System.out.printf("%5s", c);
}
}

输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
     A    B    C    D    E    F    G
A 0 5 7 12 6 8 2
B 5 0 12 9 7 9 3
C 7 12 0 17 8 13 9
D 12 9 17 0 9 4 10
E 6 7 8 9 0 5 4
F 8 9 13 4 5 0 6
G 2 3 9 10 4 6 0

A B C D E F G
A A A A F G G A
B B B A B G G B
C C A C F C E A
D G D E D F D F
E G G E F E E E
F G G E F F F F
G G G A F G G G

[D, F, E, C]

搜索最短路径: D 到 C 的最短路径,存储在前驱表的 Path[D] 这一行

  1. 先输出终点 C
  2. Path[D][C] 的前驱为 E,输出 E
  3. Path[D][E] 的前驱为 F,输出 F
  4. Path[D][F] 的前驱为 D,输出 D,因为 D 为起始点,路径搜索结束
  5. 输出的逆序即为 D 到 C 的最短路径 D, F, E, C