构建距离矩阵求最短距离

import java.util.*;

/**
 * 通过计算距离矩阵求最短路径的模板
 *
 * 以下代码认为可移动的地图是一个二维矩阵（原理适用于所有类似问题，但部分代码需要根据实际修改）
 * 移动规则为可以上下左右移动（不能超出二维矩阵）
 */
public class DistanceArray {
    // @formatter:off
    // 路径上的所有点，每个先的坐标由两个元素组成，分别表示二维数组的两个下标
    // 例如：POINTS = new int[][]{{0, 0}, {2, 5}};
    static int[][] POINTS = new int[][]{{}, {}, {}, {}, {}};
    // 距离矩阵，矩阵上的任意值的下标对应POINTS上对应的点，值表示两点间最短距离    
    static int[][] DISTANCES = new int[POINTS.length][POINTS.length];
    // 矩阵的长度和宽度
    static int N, M;
    // 矩阵中的点向上下左右四个方向移动的偏移量
    static int[][] MOVE = new int[][]{
            {0, 1}, {0, -1}, {1, 0}, {-1, 0}
    };
    // 假设二维矩阵上有5个点，从0到4有6种路径
    static int[][] ROUTE = new int[][]{
            {0, 1, 2, 3, 4},
            {0, 2, 1, 3, 4},
            {0, 1, 3, 2, 4},
            {0, 3, 1, 2, 4},
            {0, 2, 3, 1, 4},
            {0, 3, 2, 1, 4}
    };
    
    static Queue<int[]> QUEUE = new ArrayDeque<>();
    static List<int[]> NEXT_ITEMS = new ArrayList<>();
    static boolean[][] VISITED;
    
    static int MIN; // 最短路径
    // @formatter:on

    public static void main(String[] args) {
        // 初始化距离矩阵
        initDistanceArray();
        // 找最小距离
        findMin();
        // 打印结果
        System.out.printf("min distance is %d", MIN);
    }

    /**
     * 找最小值
     */
    private static void findMin() {
        MIN = Integer.MAX_VALUE;
        // 遍历所有路径
        for (int[] route : ROUTE) {
            int distance = 0;
            boolean arrived = true;
            // 遍历当前路径上的每一个点，并累计距离
            for (int i = 1; i < route.length; i++) {
                int subMin = DISTANCES[route[i]][route[i - 1]];
                if (subMin == Integer.MIN_VALUE) {
                    arrived = false;
                    break; // 不可达
                } else {
                    distance += subMin;
                }
            }

            if (arrived) {
                // 抵达重点，求最小值
                MIN = Math.min(MIN, distance);
            }
        }

        if (MIN == Integer.MAX_VALUE) {
            MIN = -1; // 所有路径不可达
        }
    }

    /**
     * 初始化距离矩阵
     */
    private static void initDistanceArray() {
        for (int start = 0; start < POINTS.length; start++) {
            // end的起始值从start + 1取，则不用考虑去重（实际就是组合算法）
            int[] stepDis = minDistance(POINTS[start], start + 1);
            for (int end = start + 1; end < POINTS.length; end++) {
                // A到B的距离等于B到A的距离，所以设置两个值
                DISTANCES[start][end] = stepDis[end];
                DISTANCES[end][start] = stepDis[end];
            }
        }
    }

    /**
     * 计算指定点到后续点的最短距离
     * @param start 指定的起始点
     * @param idx 下一个点的的POINTS的下标
     * @return 指定点到后续点的最短距离。idx之前的距离无效
     */
    private static int[] minDistance(int[] start, int idx) {
        QUEUE.clear();
        NEXT_ITEMS.clear();
        VISITED = new boolean[N][M];

        // 当前点的后续点个数，即待计算距离的个数
        int calcCount = POINTS.length - idx;
        int[] resp = new int[POINTS.length];
        Arrays.fill(resp, Integer.MIN_VALUE);

        QUEUE.offer(start);
        VISITED[start[0]][start[1]] = true;
        int step = 0;

        while (!QUEUE.isEmpty()) {
            while (!QUEUE.isEmpty()) {
                int[] curr = QUEUE.poll();

                // 判断当前的点是否到达了某个后续点
                for (int end = idx; end < POINTS.length; end++) {
                    if (curr[0] == POINTS[end][0] && curr[1] == POINTS[end][1]) {
                        resp[end] = step; // 设置距离
                        calcCount--; // 待计算量减一
                    }
                }

                if (calcCount == 0) {
                    return resp; // 全部计算完毕，返回
                }

                for (int[] shift : MOVE) {
                    int nx = curr[0] + shift[0];
                    int ny = curr[1] + shift[1];
                    if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                        // 移动后的点在二维矩阵内
                        if (!VISITED[nx][ny]) {
                            // 偏移后的点没有被访问过
                            VISITED[nx][ny] = true;
                            NEXT_ITEMS.add(new int[]{nx, ny});
                        }
                    }
                }
            }

            step++;
            QUEUE.addAll(NEXT_ITEMS);
            NEXT_ITEMS.clear();
        }

        return resp;
    }
}