Shortest path in a 2d array using Dijkstra's algorithm?

Question

This is my first time implementing Dijkstra's algorithm. Okay so here I have a simple 2D 9 by 9 array:

Starting point is 1 and we're trying to get to any green square. Red squares are walls or lava (whatever satisfies your imagination).

How do I implement this in Java?

Computer science is not my field hence I'm not a seasoned programmer so I might not know how to do some stack pushing, only loops and recursion :( please keep it easy as possible and bear with me!

Answer 1

Here's something similiar that should get you started. However, the solution presented below attempts to get to the bottom right corner. You can relax that condition to find the bottom row. You will also need to change the encoding slightly to have a unique value that represents this row.

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;
    }

}

Answer 2

I would suggest you start with writing down a method of applying dijkstras algorithm (assuming you know it in the first place) here in natural language and then start transforming it to your programming language.

The basic questions you will need to answer for that:

• What are the nodes?
• What are the connections?
• What is the weight of each connection?

Once you did this you should be able to find a (probably not efficient) solution.