java - 2D网格Java中BFS搜索最短路径

Question

我已经设法想出了一个有效的 BFS 算法，可以返回整个遍历路径，但是我不确定如何获得最短路径。

这是我的代码:

public ArrayList<Node> get_neighbours(Node node, Grid grid) {

        ArrayList<Node> neighbours = new ArrayList<>();

        int R = grid.getRl();
        int C = grid.getCl();

        int[] dr = new int[]{-1, +1, 0, 0};
        int[] dc = new int[]{0, 0, +1, -1};

        for (int i=0; i<4; i++) {
            int rr = node.getR() + dr[i];
            int cc = node.getC() + dc[i];

            if (rr < 0 || cc < 0) continue;
            if (rr >= R || cc >= C) continue;

            if (grid.getNodes()[rr][cc].getVal() == "V") continue;
            if (grid.getNodes()[rr][cc].getVal() == "X") continue;

            Node neighbour = grid.getNodes()[rr][cc];
            neighbours.add(neighbour);
        }

        return neighbours;

    }

    public Queue<Node> find_path_bfs(Node start, Node end, Grid grid) {

        Queue<Node> queue = new LinkedList<>();
        Queue<Node> path = new LinkedList<>();

        queue.add(start);
        grid.mark_visited(start.getR(), start.getC());

        while (!queue.isEmpty()) {
            Node node = queue.remove();
            path.add(node);

            if (node == end) break;

            ArrayList<Node> adj_nodes = get_neighbours(node, grid);
            for (Node n : adj_nodes) {
                if (!(n.getVal() == "V")) {
                    queue.add(n);
                    n.setVal("V");
                }
            }
        }
        return path;
    }

我看了一下这个post ，这建议也保存当前节点的路径，但我不确定如何在 Java 中实现这一点，因为我必须有一个队列将节点和节点列表一起存储为一个项目。我的Java有点生疏，所以我不确定这是否可行或者是否有更好的方法。

Answer 1

您的问题是，您现在正在使用 Queue<Node> path变量作为已访问列表，而不是路径列表。不要一边构建路径，而是存储对每个子节点的父节点的引用，然后遍历它。像这样的事情:

public ArrayList<Node> find_path_bfs(Node start, Node end, Grid grid) {

    Queue<Node> queue = new LinkedList<>();
    List<Node> path = new ArrayList<>();

    queue.add(start);
    grid.mark_visited(start.getR(), start.getC());

    Map<Node, Node> parentMap = new HashMap<>();

    Node node = start;
    parentMap.put(start, null); // start node has no parent, so we end path reconstruction here
    while (!queue.isEmpty()) {
        node = queue.remove();
        // path.add(node);

        if (node == end) break;

        ArrayList<Node> adj_nodes = get_neighbours(node, grid);
        for (Node n : adj_nodes) {
            if (!(n.getVal() == "V")) {
                queue.add(n);
                parentMap.put(n, node); // mark current node as parent to neighbor
                n.setVal("V");
            }
        }
    }

    Node curr = node;
    while (curr != null) {
        path.add(0, curr);
        curr = parentMap.get(curr);
    }

    return path;
}

我更改了 ArrayList 的路径，以便您可以在开头插入(因为您是从最后一个节点而不是第一个节点重建路径)。或者，您可以将其保留为队列并反转元素的顺序。