图-最短路径-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 为中间节点，…

// 核心: 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 算法
• 最短路径 Floyd 算法

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

Floyd 算法的代码:

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);
    }
}

输出:

     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