Print out all the cell coordinates for the shortest path

StackOverflow https://stackoverflow.com/questions/19751429

Frage

I have successfully done up a shortest path algorithm for a maze (see code below). However, I want to store the coordinates of the shortest path into the Stack parameter that is passed into my function. Could someone please advise me on how I could achieve this? Here is the maze that I am working on:

Legend: 1: Wall, 0: valid path, s: start, e: end

String[][] map = new String[][]
     {
             new String[] { "1","1","1","0","0","0","1","1","1","1" },
             new String[] { "s","0","0","0","1","1","0","0","0","1" },
             new String[] { "1","1","0","0","1","0","0","1","0","1" },
             new String[] { "1","1","1","0","0","0","0","0","0","1" },
             new String[] { "1","0","1","1","1","0","1","1","0","1" },
             new String[] { "0","0","0","0","0","0","0","0","0","1" },
             new String[] { "0","1","1","1","1","1","1","1","1","1" },
             new String[] { "0","0","0","0","0","0","0","0","0","e" },
     };

My Algorithm:

// Pre-condition: Two integers indicating the row and col number to start from,
// a 2d array of string objects representing the map of the maze,
// a 2d array of booleans mapping out the visited cells in the maze
// A string array containing the map of the maze.
// An empty Stack object
// Post-conditon: The distance of the shortest path from the current cell(start)
// to the end of the maze
public static int shortestPath(int row,int col,boolean[][] visited,String[][] map,Stack<Pair> path)
{
    if(row < 0 || row >= map.length || col < 0 || col >= map[0].length)
        return -1;
    else if(visited[row][col] == true)
        return -1;
    else if(map[row][col].equals("e"))
        return 0;
    else
    {
        // Mark the current cell as visited
        visited[row][col] = true;

        // There is a wall
        if(map[row][col].equals("1"))
            return -1;
        else
        {
            int[] pathDist = new int[4];

            // Start finding the path from the left
            int left  = 1 + shortestPath(row,col-1,visited,map,path);

            // Start searching from the right
            int right = 1 + shortestPath(row,col+1,visited,map,path);

            // Start searching from the bottom
            int down  = 1 + shortestPath(row+1,col,visited,map,path);

            // Start searching from the top
            int up    = 1 + shortestPath(row-1,col,visited,map,path);

            visited[row][col] = false;

            pathDist[0] = left;
            pathDist[1] = right;
            pathDist[2] = down;
            pathDist[3] = up;

            Arrays.sort(pathDist);

            for(Integer i : pathDist)
                if(i > 0) return i;
            return -1;
        }
    }
}

}

War es hilfreich?

Lösung

There is something fundamentally wrong with your approach: you compute all possible paths through the maze and then pick the shortest one. Try to change your input map to

String[][] map = new String[][] {
    new String[] { "s", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "e" } };

and see what happens (the algorithm will never terminate, because the number of possible paths is huge).

It would be better to use some sort of Dijkstra's, in which you keep a map of distances from the start position.

I introduced a convenience class Cell to deal with coordinates:

public static class Cell {
    public int row;     
    public int col;

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

    @Override
    public String toString() {
        return "{" + row + ", " + col + "}";
    }
}

The main algorithm, based on Dijkstra's is as follows. It follows a bread-first traversal of the maze, that is, first it visits all cells at distance 1 from the start, next round it visits all cells at distance 2 from the start, and so on.

Finding the path is a matter of starting at the end cell and just following the decreasing distances back towards the start cell.

public static int shortestPath(String[][] map, Cell start, Cell end, 
                                                           Stack<Cell> path) {
    // initialize distances array filled with infinity
    int[][] distances = new int[map.length][];
    for (int i = 0; i < map.length; i++) {
        distances[i] = new int[map[i].length];
        Arrays.fill(distances[i], Integer.MAX_VALUE);
    }

    // the start node should get distance 0
    int distance = 0;
    List<Cell> currentCells = Arrays.asList(start);

    while (distances[end.row][end.col] == Integer.MAX_VALUE
                && !currentCells.isEmpty()) {
        List<Cell> nextCells = new ArrayList<>();

        // loop over all cells added in previous round
        // set their distance 
        //    and add their neighbors to the list for next round
        for (Cell cell : currentCells) {
            if (distances[cell.row][cell.col] == Integer.MAX_VALUE 
                    && !map[cell.row][cell.col].equals("1")) {
                distances[cell.row][cell.col] = distance;
                addNeighbors(cell, nextCells, map.length, map[0].length);
            }
        }

        // prepare for next round
        currentCells = nextCells;
        distance++;
    }

    // find the path
    if (distances[end.row][end.col] < Integer.MAX_VALUE) {
        Cell cell = end;
        path.push(end);
        for (int d = distances[end.row][end.col]-1; d >= 0; d--) {
            cell = getNeighbor(cell, d, distances);
            path.push(cell);
        }
    }

    return distances[end.row][end.col];
}

I used few utility methods to keep the algorithm concise:

// add all valid neighbors of a cell to the list
    // where "valid" means: indices inside the maze
private static void addNeighbors(Cell cell, List<Cell> list, 
                                      int maxRow, int maxCol) {
    int[][] ds = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int[] d : ds) {
        int row = cell.row + d[0];
        int col = cell.col + d[1];          
        if (isValid(row, col, maxRow, maxCol))
            list.add(new Cell(row, col));
    }
}

// find the neighbor of a cell having a certain distance from the start        
private static Cell getNeighbor(Cell cell, int distance, int[][] distances) {
    int[][] ds = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int[] d : ds) {
        int row = cell.row + d[0];
        int col = cell.col + d[1];          
        if (isValid(row, col, distances.length, distances[0].length)
                && distances[row][col] == distance)
            return new Cell(row, col);              
    }
    return null;
}

// check if coordinates are inside the maze
private static boolean isValid(int row, int col, int maxRow, int maxCol) {
    return row >= 0 && row < maxRow && col >= 0 && col < maxCol;
}

My main method is as follows

public static void main(String[] args) {
    String[][] map = new String[][]
             {
                     new String[] { "1","1","1","0","0","0","1","1","1","1" },
                     new String[] { "s","0","0","0","1","1","0","0","0","1" },
                     new String[] { "1","1","0","0","1","0","0","1","0","1" },
                     new String[] { "1","1","1","0","0","0","0","0","0","1" },
                     new String[] { "1","0","1","1","1","0","1","1","0","1" },
                     new String[] { "0","0","0","0","0","0","0","0","0","1" },
                     new String[] { "0","1","1","1","1","1","1","1","1","1" },
                     new String[] { "0","0","0","0","0","0","0","0","0","e" },
             };

    Stack<Cell> path = new Stack<>();
    System.out.println(shortestPath(map, new Cell(1, 0), new Cell(7, 9), path));

    while (!path.isEmpty()) {
        System.out.print(path.pop() + ", ");
    }
}

and prints

25
{1, 0}, {1, 1}, {1, 2}, {1, 3}, {2, 3}, {3, 3}, {3, 4}, {3, 5}, {4, 5}, {5, 5}, 
{5, 4}, {5, 3}, {5, 2}, {5, 1}, {5, 0}, {6, 0}, {7, 0}, {7, 1}, {7, 2}, {7, 3}, 
{7, 4}, {7, 5}, {7, 6}, {7, 7}, {7, 8}, {7, 9},

Andere Tipps

You can create a new class Coordinate with two fields X and Y where you can store the location of the cell. Then, you can pass a list of Coordinates as a parameter to your function.

That is not the most efficient way though. For better performance, you use a matrix of predecessors. In such a matrix you keep the information of the predecessor location of the current cell. One cell can have only one predecessor, while multiple cells can have the same.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top