构建距离矩阵求最短距离
共 2181字，需浏览 5分钟
· 2022-06-08
题目
最近刷题的时候发现了这么一个场景，在一个 N * M 的二维矩阵上有5个点，并指定其起始点和终止点，求途径剩余三个点的最短路径。
具体描述见下图，S 是起始点，E 为终止点，其余三点为 A，B，C。当然原题还有很多限制，比如满足什么条件的能通过啊，什么什么条件的不能通过啊等等，此处简单化对待。
分析
可能的路径分析
通过观察可知，此题可以走的路径有6种，分别为：
• S - A - B - C - E
• S - B - A - C - E
• S - A - C - B - E
• S - C - A - B - E
• S - B - C - A - E
• S - C - B - A - E
其实，这个就是我们上一篇的集合元素的排列与组合中讲的方法。
当然，此处点的数量是固定的，我们可以简单的直接写出来路径。当然有可以用上篇文章中的代码模板求出来所有可能的路径。
两点间的最短距离
二维矩阵中的两点之间的最短距离通常可以用 BFS 算法求解，具体可以参照 BFS DFS 解题模板 的模板来实现，这里不再多讲。
多个点路径的最短距离
经分析可知，每条路径上相邻的两点的距离是最短的话，那这条路线上所有的两个相邻点的最短路径之和则就是这条路径的最短距离了。那么怎么优雅地获取每两个点之间的最短路径呢？
假设我们有这么一个矩阵，如下：
改矩阵就是我们本章节要提到的距离矩阵，每个元素表示对应的行和列的最短路径，假如已经计算完毕，那么可能长下面这个样子：
上面的矩阵中填的值只是个样子，无穷大表示两点之间不可达。那么怎么计算这些值就看我们的算法了。
算法实现
以下代码仅展示了核心算法逻辑，请不要纠结变量未初始化等问题
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;
}
}最后
• 以上的代码算法除了在二维矩阵中可以使用外，在图的结构中也能使用
• 以上代码可能还有进一步优化（时间或空间）的地方，欢迎多多交流
• 我感觉上面的代码实现是否可改为 迪杰斯特拉 算法，待验证
原文：https://www.jeremysong.cn/cn/distance-array/
欢迎关注我的公众号“须弥零一”，更多技术文章第一时间推送。