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算法求最短路径的过程如下
代码实现如下
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}