Can someone help to get Shortest Path with Obstacles?

Question

I have a 2D matrix. Given a 2D matrix where some of the elements are filled with '1' and the rest of the elements are filled with '0', except 2 elements, of which one is S (start point) and D (endpoint). Here '0' means you cannot traverse to that particular point. From a cell you can either traverse to left, right, up or down. Given two points in the matrix find the shortest path between these points.

One of the shortest paths (from S to D both exclusive) is: [(3, 2), (3, 1), (2, 1), (2, 0)]. Return null if there is no path between S and D.

I have writtes a piece of code which returns the distance to reach from S to D, my method returns int but how to return as expected output? My code:

---

public class ShortestPath {

     public static void main(String args[])
        {
            char[][] matrix = {
                {'S', '0', '1', '1'},
                {'1', '1', '0', '1'},
                {'0', '1', '1', '1'},
                {'1', '0', 'D', '1'}
            };

            int path = pathExists(matrix);

           System.out.println(path);
        }

    private static int pathExists(char[][] matrix) {

        Node source = new Node(0, 0, 0);
        Queue<Node> queue = new LinkedList<Node>();

        queue.add(source);

        while(!queue.isEmpty()) {
            Node poped = queue.poll();

            if(matrix[poped.x][poped.y] == 'D' ) {
                return poped.distanceFromSource;
            }
            else {
                matrix[poped.x][poped.y]='0';

                List<Node> neighbourList = addNeighbours(poped, matrix);
                queue.addAll(neighbourList);
            }   
        }
        return -1;
    }

    private static List<Node> addNeighbours(Node poped, char[][] matrix) {

        List<Node> list = new LinkedList<Node>();

        if((poped.x-1 > 0 && poped.x-1 < matrix.length) && matrix[poped.x-1][poped.y] != '0') {
            list.add(new Node(poped.x-1, poped.y, poped.distanceFromSource+1));
        }
        if((poped.x+1 > 0 && poped.x+1 < matrix.length) && matrix[poped.x+1][poped.y] != '0') {
            list.add(new Node(poped.x+1, poped.y, poped.distanceFromSource+1));
        }
        if((poped.y-1 > 0 && poped.y-1 < matrix.length) && matrix[poped.x][poped.y-1] != '0') {
            list.add(new Node(poped.x, poped.y-1, poped.distanceFromSource+1));
        }
        if((poped.y+1 > 0 && poped.y+1 < matrix.length) && matrix[poped.x][poped.y+1] != '0') {
            list.add(new Node(poped.x, poped.y+1, poped.distanceFromSource+1));
        }       
        return list;
    }
}
class Node {
    int x;
    int y;
    int distanceFromSource;

    Node(int x, int y, int dis) {
        this.x = x;
        this.y = y;
        this.distanceFromSource = dis;
    }
}

---

Answer 1

class Cello {
    int row;
    int col;
    public Cello(int rowIndex, int colIndex) {
        super();
        this.row = rowIndex;
        this.col = colIndex;
    }   

     @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Cello cell = (Cello) o;
            return row == cell.row &&
                    col == cell.col;
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }
}   



public class ShortestPathWithParentChildMap {

    public static void main(String[] args) {
        char[][] grid2 = {{'S', '0', '1', '1'},
                         {'1', '1', '0', '1'},
                         {'0', '1', '1', '1'},
                         {'1', '0', 'D', '1'}};


        List<int[]> path = shortestPath(grid2);

         System.out.println("Path length:" + (path.size() - 1));
            path.stream().forEach(i -> {
                System.out.println("{" + i[0] + "," + i[1] + "}");
            });
    }

    private static void bfs(char[][] grid, Cello start, List<int[]> path) {

         int[] xDirs = new int[] {0,0,1, -1};
          int[] yDirs = new int[] {1,-1, 0, 0};

            Queue<Cello> bfsQueue = new LinkedList<>();
            bfsQueue.add(start);
            HashMap<Cello, Cello> parentMap = new HashMap<>();
            boolean[][] visited = new boolean[grid.length][grid[0].length];
            Cello endCell = null;
            while(!bfsQueue.isEmpty()) {
                boolean flag = false;
                Cello from = bfsQueue.poll();

                for (int k = 0; k < xDirs.length; ++k) {
                    int nextX = from.row + xDirs[k];
                    int nextY = from.col + yDirs[k];

                    if (nextX < 0 || nextX >= grid.length || nextY < 0 
                            || nextY >= grid[0].length || grid[nextX][nextY] == '0' 
                            || visited[nextX][nextY]) {
                        continue;
                    }

                    visited[nextX][nextY] = true;
                    Cello nextCell = new Cello(nextX, nextY);
                    bfsQueue.add(nextCell);
                    //we need a way to determine from where we have reached here
                    //storing the child to parent mapping, this will be used to retrieve the entire path
                    parentMap.put(nextCell, from);
                    //if (grid[nextX][nextY] == 'E') 
                    if (grid[nextX][nextY] == 'D') {
                        endCell = new Cello(nextX, nextY);
                        flag = true;
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            }
            Stack<Cello> stack = new Stack<>();
            stack.push(endCell);

            //build the path from destination to source
            while (true) {
                Cello fromCell = parentMap.get(endCell);
                stack.push(fromCell);
                if (fromCell == start) break;
                endCell = fromCell;
            }
           //reverse the above path and convert as List<int[]>
            while (!stack.isEmpty()) {
                Cello p = stack.pop();
                path.add(new int[] {p.row, p.col});
            }
    }

    private static List<int[]> shortestPath(char[][] grid) {
        ArrayList<int[]> path = new ArrayList<>();
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (grid[i][j] == 'S') {
                    bfs(grid, new Cello(i, j), path);
                }
            }
        }
        return path;
    }

}

Output is:
Path length:5
{0,0}
{1,0}
{1,1}
{2,1}
{2,2}
{3,2}

Answer 2

You are essentially implementing BFS (Breadth first search) to detect the existence of a path from the source (S) to the destination (D). All you need to trace the path is maintain a parent Node in your Node definition.

Set the starting node's parent to null. Then, as your discover nodes in your BFS from the current node, set the parent of the discovered node to the current node.

Now, if your search is successful (i.e. you hit D in your search), just traverse the chain of parent nodes backwards from D until you hit S, throwing the visited parents into a stack.

Finally just keep popping the stack until it turns empty to get the nodes on the path from S to D.

Answer 3

you are getting only the distance because you are only returning the distance between source and Destination. follow these to solve and print the route as well;

algo 1:-

    just print the node value when you are updating the distance calculation. 

algo 2:-

     1. create a queue to store the nodes. 
     2. insert the  node point of S to queue
     3. keep adding to the node value to queue when you are adding the value to distance. unless reaching to 'D'
     4. now just print the nodes from the queue which will print the path structure.