记录生活中的点点滴滴

0%

弗洛伊德算法

前些天做了阿里的笔试,第一题a了,第二题好像需要借助弗洛伊德算法去求解,当时写了挺长时间没搞定,这次专门记录一下弗洛伊德算法的实现。

弗洛伊德算法它通过3重循环,k为中转点,v为起点,w为终点,循环比较D[v] [w] 和 D[v] [k] + D[k] [w] 最小值,如果D[v] [k] + D[k] [w] 为更小值,则更改。如下所示:

大致思想就是先以A为基准节点,遍历二维数组,看是否能通过A连接两个不相等的i j,让它们之间通过中间节点A的距离比原有的dp[i] [j]小,就替换为 dp[i] [k] + dp[i] [k]即可,k为A的下标。

所以就是三层for循环,但是要注意我们上述的思想中,第一层也就是最外层是k,i、j分别为第二层和第三层。k能不能在内层,也就是第三层,首先根据动态规划的思想,它必须为内层,见:深入理解Floyd算法思路

我再说说我的理解,因为本来我们上面的思路来,肯定是没问题的,把上述的思想变成代码,则k就是在最外层,如果k为内层,我们可以看一个例子:

我们看节点0和节点1之间的距离,本来初始化为INF,然后如果我们把k放在内层,当i为0,j为1,然后遍历k,并且只有这一次机会了,后续i++,j++,dp[0] [1] 这个距离根本轮不到它。所以这次就算我们遍历k,看看是否有用?只会当k为2时,dp[0] [1] 才会借助节点2变成1+4也就是5,但是我们一眼就能看出来,正确答案应该是借助节点3和节点4,距离为2+1+1也就是4。所以k不能为最内层,因为弗洛伊德算法要求我们先从一个基准点去遍历整个二维表,而不是先确定两个节点,遍历k去寻找最小值!

还有一个问题就是:

初始化的时候我们需要先填充二维数组的值全部为 Integer.MAX_VALUE,因为是二维数组,我们想到可以先填充一个一维数组,然后再用这个一维数组去填充二维数组,但是会出现一个问题:就是因为数组不是基本类型,我们填充完毕之后,假设修改了arr【0】【0】,那么不好意思,arr【1】【0】、arr【2】【0】、、、等都会变成我们修改的值,因为它们指向的同一个地址。所以,关于填充的话,我们还是老老实实用for循环填充算了!

综上所述,我们来做一道题,看下面的图,根据输入去返回弗洛伊德算法后的二维表,下面是输入和图:

输入第一行就是节点数量n(节点为0到n-1)和边数量m,然后就是m条边:

1
2
3
4
5
6
7
5 6
0 2 1
0 4 2
2 4 5
4 3 1
1 3 1
1 2 4

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
public class FloydDemo {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//n个节点 0到n-1
int n = scanner.nextInt();
//m条边
int m = scanner.nextInt();
//图的矩阵
int[][] arr = new int[n][n];
//初始化先填充最大值
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = i==j ? 0 : 1000;
}
}

//获得输入并填充相对应矩阵
for (int i = 0; i < m; i++) {
int x1 = scanner.nextInt();
int x2 = scanner.nextInt();
int dis = scanner.nextInt();
arr[x1][x2] = dis;
arr[x2][x1] = dis;
}
System.out.println("输出填充前的矩阵:");
//输出填充前的矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arr[i][j]+"\t");
}
System.out.println();
}
//进行弗洛伊德算法
//以k为中间节点选择取最小值
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = Math.min(arr[i][j],arr[i][k]+arr[k][j]);
}
}
}

System.out.println("输出填充后的矩阵:");
//输出填充后的矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arr[i][j]+"\t");
}
System.out.println();
}
}
}

参考博客:https://blog.csdn.net/jeffleo/article/details/53349825

另外,迪杰斯特拉算法的讲解:https://www.bilibili.com/video/BV1q4411M7r9