Dijkstra算法在2D数组中求最短路径？

Question

Dijkstra算法在2D数组中求最短路径？

javashortest-pathdijkstra

3

这是我第一次实现Dijkstra算法。好的，这里有一个简单的2D 9x9数组: 9 by 9 array

起点是1，我们要到达任何一个绿色方块。红色方块是墙或熔岩（任何你想象的东西）。

如何在Java中实现它？

计算机科学不是我的领域，因此我不是一个经验丰富的程序员，所以我可能不知道如何进行一些堆栈推送，只会使用循环和递归 :( 请尽可能简单易懂，并耐心等待我！

- meiryo

3个回答

3

我建议你先用自然语言写下应用Dijkstra算法的方法（假设你已经了解该算法），然后再将其转化成你所使用的编程语言。

为此，您需要回答以下基本问题：

- 节点是什么？ - 连接是什么？ - 每个连接的权重是多少？

完成此步骤后，您应该能够找到一个（可能不是很高效的）解决方案。

- Vespasian

可以找到一个高效的解决方案：Dijkstra！请看我的回答。 - Karussell

1

最佳解决方案确实是使用Dijkstra或AStar算法，但需要使用不同的结束条件。因此，您需要编写if(targetNodes.contains(u)) break;而不是if(target == u) break;

(参见维基百科：如果我们只对源顶点和目标顶点之间的最短路径感兴趣，那么当u=target时，我们可以在第13行终止搜索。)

这已经在我的项目中实现了...哦，这是作业吗？

- Karussell

嘿，我正在尝试在游戏中实现Dijkstra算法，你能帮我吗？问题链接 - Murhaf Sousli

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btiernay · Accepted Answer

这里有一个类似的问题可以让你开始思考。然而，下面介绍的解决方案试图到达右下角，你可以放松条件，以找到底部行。您还需要稍微更改编码，以获得代表此行的唯一值。

public class MazeSolver {

    final static int TRIED = 2;
    final static int PATH = 3;

    // @formatter:off
    private static int[][] GRID = { 
        { 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1 },
        { 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1 },
        { 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 },
        { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1 },
        { 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1 },
        { 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
        { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } 
    };
    // @formatter:off

    public static void main(String[] args) {
        MazeSolver maze = new MazeSolver(GRID);
        boolean solved = maze.solve();
        System.out.println("Solved: " + solved);
        System.out.println(maze.toString());
    }

    private int[][] grid;
    private int height;
    private int width;

    private int[][] map;

    public MazeSolver(int[][] grid) {
        this.grid = grid;
        this.height = grid.length;
        this.width = grid[0].length;

        this.map = new int[height][width];
    }

    public boolean solve() {
        return traverse(0,0);
    }

    private boolean traverse(int i, int j) {
        if (!isValid(i,j)) {
            return false;
        }

        if ( isEnd(i, j) ) {
            map[i][j] = PATH;
            return true;
        } else {
            map[i][j] = TRIED;
        }

        // North
        if (traverse(i - 1, j)) {
            map[i-1][j] = PATH;
            return true;
        }
        // East
        if (traverse(i, j + 1)) {
            map[i][j + 1] = PATH;
            return true;
        }
        // South
        if (traverse(i + 1, j)) {
            map[i + 1][j] = PATH;
            return true;
        }
        // West
        if (traverse(i, j - 1)) {
            map[i][j - 1] = PATH;
            return true;
        }

        return false;
    }

    private boolean isEnd(int i, int j) {
        return i == height - 1 && j == width - 1;
    }

    private boolean isValid(int i, int j) {
        if (inRange(i, j) && isOpen(i, j) && !isTried(i, j)) {
            return true;
        }

        return false;
    }

    private boolean isOpen(int i, int j) {
        return grid[i][j] == 1;
    }

    private boolean isTried(int i, int j) {
        return map[i][j] == TRIED;
    }

    private boolean inRange(int i, int j) {
        return inHeight(i) && inWidth(j);
    }

    private boolean inHeight(int i) {
        return i >= 0 && i < height;
    }

    private boolean inWidth(int j) {
        return j >= 0 && j < width;
    }

    public String toString() {
        String s = "";
        for (int[] row : map) {
            s += Arrays.toString(row) + "\n";
        }

        return s;
    }

}