如何将网格中单元格的邻居存储到优先级队列中

Question

假设我有一个 4 x 4 的网格，所以有 16 个单元格。每个单元格包含一个介于 1,5 之间的值。例如

     0 1 2 3
     _ _ _ _
0 - |2|1|3|2|
1 - |1|3|5|1|
2 - |5|2|1|4|
3 - |2|4|2|1|

现在我知道我需要用到Dijkstra算法了。此外，为了优化这一点，我需要使用优先级队列。

我的目标是找到每个单元格到目的地的最短总和。源在网格和目的地上也可以是随机的。（即不总是从左上角到右下角）。

我处理过使用相邻矩阵的图形。但是，使用此网格创建相邻矩阵是否明智？即，将所有不是邻居的字段设置为无穷大。将信元插入优先级队列的最充分方法是什么？会是{(row,col), distance}吗？

根据我的理解澄清一下，优先级队列将存储最佳路径？所以细胞和累积距离。因为，Dijstra 的算法使用 BFS，在这种情况下将搜索所有邻居的最短距离。

Answer 1

创建一个 'Node' 具有 3 个字段（行、列、距离）并实现 Comparable 的 class。然后使用 Use PriorityQueue<Node>:

import java.util.PriorityQueue;

class Main {

    public static void main(String[] args) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(2, 3, 12));
        pq.add(new Node(0, 9, 1));
        pq.add(new Node(4, 0, 8));

        System.out.println(pq.poll().getDistance()); //prints 1
    }
}

class Node  implements Comparable<Node>{

    private final int row, col, distance;

    public Node(int row, int col, int value) {
        this.row = row;
        this.col = col;
        distance = value;
    }

    int getDistance() {
        return distance;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(distance, other.distance);
    }
}

或者将 Comperator 设置为优先级队列，这样 Node 就不必实现 Comparable：

import java.util.PriorityQueue;

class Main {

    public static void main(String[] args) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Node::compare);
        pq.add(new Node(2, 3, 12));
        pq.add(new Node(0, 9, 1));
        pq.add(new Node(4, 0, 8));

        System.out.println(pq.poll().getDistance()); //prints 1
    }
}

class Node{

    private final int row, col, distance;

    public Node(int row, int col, int value) {
        this.row = row;
        this.col = col;
        distance = value;
    }

    int getDistance() {
        return distance;
    }

    public static int compare(Node o1, Node o2) {
        return Integer.compare(o1.getDistance(), o2.getDistance());
    }
}

您还可以使用 lambda 表达式来设置计算器：

PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2)->Integer.compare(o1.getDistance(), o2.getDistance()));

三个选项都有效。

如何将网格中单元格的邻居存储到优先级队列中

How to store neighbours of a cell in a gird into a priority queue

java

algorithm

dijkstra

priority-queue

data-structures