算法题:利用 Dijkstra 算法求解矩阵中的最短路径

1 题目背景

前几天,一个朋友问了我个关于最短路径的算法题:

聊天记录

我随便一看,这不动态规划嘛!!于是乎十分钟给他写了个 demo 出来。但是晚上在被窝里一想,不对!这道题并没有限定管理员只能向下或向右走,因此每个仓库的最小权重会依赖他上、下、左、右四个仓库的最小权重。因此需要当做图数据结构来处理。

知道了问题所在,接下来就是算法选择了,我们先来看题干:

2 题目题干

公司有一个仓库划分为在 6 行 6 列共 36 个货区,库管每天上班需要对仓库进行一次抽盘每个货区前一天下班会更新存储货物件数,第二天上班时,库管要做一次抽盘,从 A1 货区开始,穿过必经的货区到达 F6 货区结束,请做一个程序实现,帮库管找到一条盘点路径,目的是走过这个路径时对经过货区同步做货物盘点用时最快,比如 3 月 1 日上班每个货区货物量化后得到的盘点用时权重如下表所示:

仓库

请编程实现这个辅助工具,输出这个初始用时权重数据下,客观需要走过的路径,以及最后的最短用时。

对于这种所有权重都是非负数的体,很适合用 Dijkstra 算法求解。

3 Dijkstra 算法简介

Dijkstra 算法是一种用于解决单源最短路径问题的经典算法,由荷兰计算机科学家 Edsger W. Dijkstra 于 1956 年提出。该算法可以找出从起始顶点到图中所有其他顶点的最短路径。

基本思想是从起始顶点开始,逐步扩展到尚未确定最短路径的顶点,通过不断更新起始顶点到其他顶点的最短距离信息来求解最短路径。

Dijkstra 算法的步骤如下:

  • 初始化:将起始顶点的最短距离设置为 0,其他顶点的最短距离设置为无穷大。
  • 选择当前最短路径:从尚未确定最短路径的顶点中选择距离起始顶点最近的顶点,将其标记为已确定最短路径。
  • 更新距离:对于与当前顶点相邻的顶点,如果通过当前顶点到达它们的距离比原先估计的距离更短,则更新其距离。
  • 重复步骤 2 和步骤 3,直到所有顶点都被标记为已确定最短路径或者无法再找到新的最短路径为止。

Dijkstra 算法的时间复杂度取决于如何实现图的表示和最小堆的使用。通常情况下,在稠密图中,使用邻接矩阵表示图,时间复杂度为 O(V^2),其中 V 是顶点的数量;在稀疏图中,使用邻接表表示图,并结合最小堆,时间复杂度可以优化至 O((V+E)logV),其中 E 是边的数量。

了解了 Dijkstra 算法的概念,接下来我们再来分析这道题。首先,我们题中的这个“仓库”的矩阵,并不等同于图的 邻接矩阵。我们需要把整个“仓库”矩阵看做一个图,每个“货区”都是图上的一个顶点,而每个顶点上的“货物数量”就是该节点到其上、下、左、右四个顶点的边的权重(这句话有点绕,希望大家好好理解)。

有了这个概念,接下来我们再了解一下 Dijkstra 算法必须的优先队列。

4 Java PriorityQueue 详解

PriorityQueue 是 Java 类库中的一个优先队列,将来我们要通过这个类完成解题。

4.1 优先队列的概念(小顶堆)

优先队列是一种特殊的队列,它与普通队列的主要区别在于优先队列中的元素是按照优先级顺序排列的,而不是按照插入顺序。在优先队列中,具有更高优先级的元素会先被处理,而具有相同优先级的元素则可能按照其插入顺序处理。

java.util.PriorityQueue 为例,其排序操作是在插入时完成的:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

以通过默认比较器排序的实现为例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// k 为当前队列元素的总数量,x 为待插入的数据
private void siftUpComparable(int k, E x) {
    // key 即待插入元素的值
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) { 
        int parent = (k - 1) >>> 1; // 找到 k 位置的父节点
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0) // 如果已经比父节点大了,直接插入
            break;
        queue[k] = e;  // 如果
        k = parent;
    }
    queue[k] = key;
}

可见,PriorityQueue 会在插入过程中,通过小顶堆选择合适的位置。

小顶堆是一种二叉堆的特殊形式,它满足以下两个性质:

  • 堆的顶部元素(根节点)是堆中的最小元素。
  • 对于堆中的任意节点 i,其父节点的值小于等于节点 i 的值。

而小顶堆模型上较 BST 宽松,它只需要保证每个父节点比他的两个子节点小即可,也就是 P(i) < P(2 * i + 1) && P(i) < P(2 * i + 2)。以子节点的视角来看,那就是每个子节点的值必须大于它的父节点,即 P(i) > P((i - 1) / 2)

所以上述算法就清晰明了了,该算法首先设想将待插入元素放入 k 索引处,然后循环遍历。每次循环都会寻找 k 索引位置的父节点:

  • 如果 k 节点的值大于父节点,则插入返回;
  • 否则交换 k 与其父元素,继续下一轮判断,直到待插入元素大于其父节点时结束。

通过这样的设计,小顶堆实现了堆顶元素始终保持最小的特性,且不保证除堆顶外其他节点的有序性,因此插入性能较高(只需要沿着一条路径交换)。

以下是小翎哥随机插入几条数据后的小顶堆示意图:

小顶堆

4.2 PriorityQueue 常用 API 详解

PriorityQueue API

我们重点关注其 offer() 方法和 poll() 方法,他们分别用来插入数据和弹出权重最小的数据。

5 代码实现

铺垫了这么多,接下来可以进入正题,完成代码的编写了。

首先,为了方便验证结果,我们创建一个比题目要求更大的、足够明显的仓库矩阵数组:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class DijkstraDemo {

    public static void main(String[] args) {

        int[][] matrix = new int[][] {
            {  1,255,255,255,255,255,255,255,255,255,255,255},
            {  1,  1,  1,  1,255,255,255,255,255,255,255,255},
            {255,255,255,  1,255,255,255,255,255,255,255,255},
            {255,255,255,  1,255,255,255,255,255,255,255,255},
            {255,  1,  1,  1,255,255,255,255,255,255,255,255},
            {255,  1,255,255,255,255,255,255,255,255,255,255},
            {255,  1,  1,  1,  1,255,  1,  1,  1,  1,255,255},
            {255,255,255,255,  1,255,  1,255,255,  1,255,255},
            {255,255,255,255,  1,  1,  1,255,255,  1,255,255},
            {255,255,255,255,255,255,255,255,255,  1,255,255},
            {255,255,255,255,255,255,255,255,255,  1,  1,255},
            {255,255,255,255,255,255,255,255,255,255,  1,  1},
        };
    }
}

这是一个 12x12 矩阵,而且显然最佳路径为所有权重为 1 的货区所组成的通路,也就是说最终的输出结果应该为 31 x 1 == 31

然后编写 solve 方法进行计算:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public static int solve(int[][] matrix) {
    int n = matrix.length;
    // Dijkstra 算法依赖的 1:1 矩阵,存储某个坐标已经探索的最小权重
    int[][] distances = new int[n][n];
    for (int[] distance : distances) {
        // 默认值为无穷大,表示还未探索过
        Arrays.fill(distance, Integer.MAX_VALUE);
    }
    distances[0][0] = matrix[0][0]; // 存入起点状态

    // 创建一个优先队列,队列元素为矩阵坐标,比较对象为坐标对应的已探索的 distances 权重
    PriorityQueue<int[]> pq = new PriorityQueue<>(
            Comparator.comparingInt(a -> distances[ a[0] ][ a[1] ]));
    // 坐标通过一个包含两个元素的一维数组表示
    pq.offer(new int[] {0, 0}); // 先把起点权重插入
    // Dijkstra 算法,遍历所有已探寻路径的末端
    while (!pq.isEmpty()) {
        // 优先选择当前总权重最小的路径末端
        int[] current = pq.poll();
        // 定义上下左右四个方向
        int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        for (int[] direction : directions) {
            int nextX = current[0] + direction[0];
            int nextY = current[1] + direction[1];
            // 更新下一跳的 x、y,注意对边界的处理
            if (nextX >=0 && nextX < n && nextY >= 0 && nextY < n) {
                // 计算当前权重,加上下一个方向节点权重的和,作为新的最小权重
                int newDist = matrix[nextX][nextY] + distances[ current[0] ][ current[1] ];
                // 如果新的最小权重小于当前已记录的最小权重,则更新
                // 不用担心折回去被统计到,因为折回去的肯定不满足下边的表达式
                if (newDist < distances[nextX][nextY]) {
                    distances[nextX][nextY] = newDist;
                    pq.offer(new int[] {nextX, nextY});
                }
            }
        }
    }

    // 迭代完成后,返回右下角坐标的最小权重
    return distances[n-1][n-1];
}

注释很详细,所以就不再赘述了,最终我们在 main 方法中调用这个方法:

1
2
int solve = solve(matrix);
System.out.println(solve);

打印结果如下:

1
2
3
31

Process finished with exit code 0

结果与预想的完全一致!

6 严谨测试

在上述矩阵的基础上,我们尝试加一些干扰,但不改变最短路径:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int[][] matrix = new int[][] {
    {  1,255,255,255,255,255,255,255,255,255,255,255},
    {  1,  1,  1,  1,255,255,255,255,255,255,255,255},
    {255,255,255,  1,255,255,255,255,255,255,255,255},
    {255,255,255,  1,255,255,255,255,255,255,255,255},
    {255,  1,  1,  1,255,255,255,  1,  1,  1,255,255}, //<-- 添加一个干扰环
    {255,  1,255,255,255,255,255,  1,255,  1,255,255},
    {255,  1,  1,  1,  1,255,  1,  1,  1,  1,255,255},
    {255,255,255,255,  1,255,  1,255,255,  1,255,255},
    {255,255,255,255,  1,  1,  1,255,255,  1,  1,255}, //<-- 添加一个岔路干扰
    {255,255,255,255,255,255,255,255,255,  1,255,255},
    {255,255,255,255,255,255,255,255,255,  1,  1,255},
    {255,255,255,255,255,255,255,255,255,255,  1,  1},
};

最终测试的结果依旧为 31,说明算法逻辑正确。


欢迎关注我的公众号,第一时间获取文章更新:

微信公众号

相关内容