Java数字迷宫最短路径代码修正求助：仅找到首路径而非最短

你的问题很典型：DFS（深度优先搜索）会优先深入探索一条路径，找到的第一个可行路径不一定是最短的。要找到唯一的最短路径，最合适的算法是BFS（广度优先搜索）——它按层遍历节点，第一次到达目标节点时的路径必然是最短的。

问题根源分析 #

你当前的代码用栈+DFS实现，会沿着一条路径一直走到底，直到找到终点。但迷宫里可能存在多条路径，DFS找到的第一条路径往往是较长的那条（比如你的示例中绕了一大圈），而BFS能保证每一步都探索当前距离起点最近的节点，所以第一次碰到终点时的路径就是最短的。

修正后的代码实现 #

我们用BFS来实现，同时记录每个节点的前驱节点，这样到达终点后可以回溯出完整的最短路径：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class FindShortestPath {
    // 节点类，记录坐标、前驱节点（用于回溯路径）
    private static class Node {
        int row;
        int col;
        Node parent;

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

    // 判断坐标是否在迷宫范围内
    private static boolean isValid(int[][] maze, int row, int col) {
        return row >= 0 && row < maze.length && col >= 0 && col < maze[0].length;
    }

    // BFS寻找最短路径
    private static Node findShortestPath(int[][] maze) {
        int rows = maze.length;
        int cols = maze[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Queue<Node> queue = new LinkedList<>();

        // 起点是(0,0)，前驱为null
        Node startNode = new Node(0, 0, null);
        queue.add(startNode);
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            int currentRow = current.row;
            int currentCol = current.col;

            // 到达目标节点（值为-1），返回当前节点
            if (maze[currentRow][currentCol] == -1) {
                return current;
            }

            int step = maze[currentRow][currentCol];
            // 四个方向：右、下、左、上
            int[][] directions = {
                {0, step},   // 右
                {step, 0},   // 下
                {0, -step},  // 左
                {-step, 0}   // 上
            };

            for (int[] dir : directions) {
                int newRow = currentRow + dir[0];
                int newCol = currentCol + dir[1];
                if (isValid(maze, newRow, newCol) && !visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;
                    queue.add(new Node(newRow, newCol, current));
                }
            }
        }

        // 没有找到路径
        return null;
    }

    // 回溯路径并输出
    private static void printPath(Node endNode) {
        if (endNode == null) {
            System.out.println("No Solution Possible.");
            return;
        }

        // 用栈反转路径（因为回溯是从终点到起点）
        Stack<Node> pathStack = new Stack<>();
        Node current = endNode;
        while (current != null) {
            pathStack.push(current);
            current = current.parent;
        }

        // 输出路径
        while (!pathStack.isEmpty()) {
            Node node = pathStack.pop();
            System.out.printf("(%d %d) ", node.row, node.col);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[][] maze = {{1,1,1,1,1}, {1,1,1,1,1}, {1,1,1,1,1}, {1,1,1,1,3}, {4,1,1,3,-1}};
        Node endNode = findShortestPath(maze);
        printPath(endNode);
    }
}

代码说明 #

• BFS核心逻辑：用队列存储待探索的节点，每次取出队首节点，探索它四个方向的可达节点（根据当前单元格的步数移动），标记为已访问后加入队列。
• 路径回溯：每个节点记录它的前驱节点，当到达终点时，从终点回溯到起点，再用栈反转得到从起点到终点的顺序。
• 访问标记：避免重复访问同一个节点，防止循环和冗余计算。

测试结果 #

运行代码后，输出的最短路径与你的期望完全一致：

(0 0) (1 0) (2 0) (3 0) (4 0) (4 4) 

内容的提问来源于stack exchange，提问作者MAlhamry