Floyd算法，也称为Floyd-Warshall算法，是一种用于解决图中所有节点对之间最短路径问题的动态规划算法。该算法可以计算出图中任意两个节点之间的最短路径长度。
Floyd算法的基本思想是通过中间节点的遍历来逐步优化路径长度。算法的核心是一个二维数组，称为距离矩阵，用于存储节点之间的最短路径长度。算法的执行过程中，不断更新距离矩阵中的值，直到得到最终的最短路径结果。
下面是Floyd算法的基本步骤：
初始化距离矩阵：将图中节点之间的直接距离填入距离矩阵，如果两个节点之间没有直接边相连，则距离矩阵中对应位置的值为无穷大（表示不可达）。
通过中间节点遍历：对于每一个节点k，遍历距离矩阵中的每一对节点i和j，尝试通过节点k来优化节点i和节点j之间的路径长度。具体做法是比较节点i直接到节点j的路径长度与节点i经过节点k再到节点j的路径长度，如果后者更短，则更新距离矩阵中节点i和节点j之间的路径长度为更短的路径长度。
重复遍历：重复执行步骤2，每次选择一个新的中间节点k，直到遍历完所有节点。这样，距离矩阵中的值将逐步被更新，最终得到所有节点对之间的最短路径长度。
输出最短路径：根据最终的距离矩阵，可以得到任意两个节点之间的最短路径长度。如果需要还原具体的路径，可以使用额外的数据结构（如前驱矩阵）来记录最短路径的信息。
Floyd算法的时间复杂度为O(n^3)，其中n表示图中节点的数量。它适用于解决稠密图（边数较多）的最短路径问题，但对于稀疏图（边数较少）来说，可能存在更高效的算法。
Java模板
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
| import java.util.Scanner;
public class Solution {
static int m, n, u, v, w;
final static int INF = Integer.MAX_VALUE;
static long[][] g = null;
static void floyd() {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] > g[i][k] + g[k][j]) {
g[i][j] = g[i][k] + g[k][j];
}
}
}
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
m = cin.nextInt();
g = new long[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = i == j ? 0 : INF;
}
}
while (m-- > 0) {
u = cin.nextInt();
v = cin.nextInt();
w = cin.nextInt();
if (w < g[u][v]) {
g[u][v] = g[v][u] = w;
}
}
floyd();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.printf("%d ", g[i][j]);
}
System.out.println();
}
}
}
|
执行结果：
1
2
3
4
5
6
7
8
9
10
11
12
| 4
4
0 2 2
1 0 1
1 3 10
2 3 3
0 1 2 5
1 0 3 6
2 3 0 3
5 6 3 0
进程已结束,退出代码0
|
Leetcode.399 除法求值
题目链接 本题有多种解决思路，这里采用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
| import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
int nvars = 0;
Map<String, Integer> vars = new HashMap<>();
int n = equations.size();
for (int i = 0; i < n; i++) {
if (!vars.containsKey(equations.get(i).get(0))) {
vars.put(equations.get(i).get(0), nvars++);
}
if (!vars.containsKey(equations.get(i).get(1))) {
vars.put(equations.get(i).get(1), nvars++);
}
}
double[][] g = new double[nvars][nvars];
for (int i = 0; i < nvars; i++) {
Arrays.fill(g[i], -1.0);
}
for (int i = 0; i < n; i++) {
int va = vars.get(equations.get(i).get(0));
int vb = vars.get(equations.get(i).get(1));
g[va][vb] = values[i];
g[vb][va] = 1.0 / values[i];
}
for (int k = 0; k < nvars; k++) {
for (int i = 0; i < nvars; i++) {
for (int j = 0; j < nvars; j++) {
if (g[i][k] > 0 && g[k][j] > 0) {
g[i][j] = g[i][k] * g[k][j];
}
}
}
}
int queriesCount = queries.size();
double[] ret = new double[queriesCount];
for (int i = 0; i < queriesCount; i++) {
List<String> query = queries.get(i);
double res = -1.0;
if (vars.containsKey(query.get(0)) && vars.containsKey(query.get(1))) {
int ia = vars.get(query.get(0));
int ib = vars.get(query.get(1));
if (g[ia][ib] > 0) {
res = g[ia][ib];
}
}
ret[i] = res;
}
return ret;
}
}
|