最短路径之Floyd算法

学习数据结构与算法
2021-05-17 14:29 · 阅读时长4分钟
小课

Floyd算法是一种求多源最短路径的算法,并且支持有负权的图,但不可以存在负权回路,它是一种动态规划算法,时间复杂度是O(V3),V是顶点的个数。

主要思路是,对于任意两个顶点i和顶点j,距离为d[i][j],我们遍历所有顶点,如果发现某个顶点k满足d[i][j]>d[i][k]+d[k][j]则更新d[i][j]为d[i][k]+d[k][j],当所有顶点都遍历完成后,就得到任意两个顶点之间的最短路径。

比如下面这个图,使用Floyd算法求最短路径的过程如下

最短路径之Floyd算法
最短路径之Floyd算法
最短路径之Floyd算法
最短路径之Floyd算法
最短路径之Floyd算法
最短路径之Floyd算法
最短路径之Floyd算法
1/6

代码实现如下

1package floyd;
2
3import java.util.Arrays;
4
5public class Main {
6
7    /**
8     * 这里使用10000代表无穷大,因为在Java中使用Integer.MAX参与运算会造成溢出
9     */
10    private static final int INF = 10000;
11
12    public static void main(String[] args) {
13        int[][] map = new int[][]{
14                {0, 1, 12, INF, INF, INF},
15                {INF, 0, 9, 3, INF, INF},
16                {INF, INF, 0, INF, 5, INF},
17                {INF, INF, 4, 0, 13, 15},
18                {INF, INF, INF, INF, 0, 4},
19                {INF, INF, INF, INF, INF, 0}
20        };
21        int[][] distance = floyd(map);
22        for (int[] dis : distance) {
23            System.out.println(Arrays.toString(dis));
24        }
25    }
26
27    /**
28     * floyd算法求最短路径
29     *
30     * @param map 图,邻接矩阵表示
31     * @return 所有点之间的最短距离
32     */
33    private static int[][] floyd(int[][] map) {
34        int n = map.length;
35        int[][] d = new int[n][n];
36        for (int i = 0; i < n; i++) {
37            d[i] = Arrays.copyOf(map[i], n);
38        }
39        for (int k = 0; k < n; k++) {
40            /**
41             * 如果顶点i,j之间当前最短路径distance[i,j],
42             * 大于从顶点k中转的距离distance[i,k]+distance[k,j],
43             * 则更新distance[i,j]=distance[i,k]+distance[k,j]
44             */
45            for (int i = 0; i < n; i++) {
46                for (int j = 0; j < n; j++) {
47                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
48                }
49            }
50        }
51        return d;
52    }
53}
注意: 这个Java运行环境不支持自定义包名,并且public class name必须是Main
Floyd最短路径