I was trying to solve this problem in Java:Given a 2-D array of black and white entries representing a maze with designated entrance and exit points, find the shortest path from entrance to exit, if one exists. The black entry represents a wall and the white entry represents an open space.I tried to solve it using a variant of the Breadth-First-Search algorithm, where from a starting position, I examine all its possible adjacent positions. If the adjacent spot has not been visited(a Map containing the spaces that have been visited) or is not in the in-process queue, I add it to the in-process queue. If I encounter an adjacent spot that has been visited, I examine its 'weight', if the weight of the adjacent spot is less than one added to the current weight of the space in process, I update the weight of the visited node. I keep on doing this until I encounter the destination or all the nodes in the maze have been processed.I have crafted my algorithm as follows, it will be great if I could get some feedback on refining it further.import java.util.Set;import java.util.List;import java.util.Queue;import java.util.Map;import java.util.HashSet;import java.util.ArrayList;import java.util.LinkedList;import java.util.HashMap;public class ShortestMazePath{    class Node{        private final int x;        private final int y;        private final int weight;        private final Node previous;        Node(int x,int y,Node previous,int weight){            this.x = x;            this.y = y;            this.previous = previous;            this.weight = weight;        }        public int getX(){            return this.x;        }        public int getY(){            return this.y;        }        public int getWeight(){            return this.weight;        }        public Node getPrevious(){            return this.previous;        }        @Override public boolean equals(Object o){            if(o == null){              return false;            }            if(!(o instanceof Node)){              return false;            }            final Node n = (Node)o;            return ((n.x == x) && (n.y == y));        }        @Override public int hashCode(){            int result = 17;            result = 31*result+x;            result = 31*result+y;            return result;        }        @Override public String toString(){          return Current X is +this.x+ Current Y is +this.y;        }     }       private boolean isValid(boolean[][] maze,int m,int n,Node node){        return (node.getX() >=0 && node.getX() < m) &&               (node.getY() >= 0 && node.getY() < n) &&            maze[node.getX()][node.getY()];    }    private Node updatedNode(Node currentNode,Node visitedNode){        if(currentNode.weight + 1 < visitedNode.weight){            return new Node(visitedNode.getX(),                    visitedNode.getY(),                    currentNode,                    currentNode.weight + 1);        }else{            return visitedNode;        }    }       private Set<Node> getNeighbors(Node current,int m,int n,boolean[][] maze){        int currentX = current.getX();        int currentY = current.getY();        int currentWeight = current.getWeight();        Set<Node> validNeighbors = new HashSet<Node>();        List<Node> neighbors = new ArrayList<Node>(){{                     add(new Node(currentX-1,currentY,current,currentWeight));                     add(new Node(currentX+1,currentY,current,currentWeight));                     add(new Node(currentX,currentY+1,current,currentWeight));                     add(new Node(currentX,currentY-1,current,currentWeight));}};        for(Node node:neighbors){            if(isValid(maze,m,n,node)){                validNeighbors.add(node);            }        }           return validNeighbors;      }    private static boolean[][] createMaze(){        boolean[][] maze = {{true,true,true},                    {true,true,false},                    {true,true,false}};        return maze;    }    private void printQueue(Set<Node> q){        for(Node n:q){            System.out.println(Queue contains node+ n);        }    }    private void printMap(Map<Node,Node> m){        for(Map.Entry<Node,Node> entry:m.entrySet()){            System.out.println(visited contains node +entry.getKey());        }    }    public Node findPath(boolean[][] maze,int p,int q,Node start,Node end){        Queue<Node> inProcess = new LinkedList<Node>();        Map<Node,Node> visited = new HashMap<Node,Node>();        Set<Node> inProcessQueue = new HashSet<Node>();        inProcess.add(start);        inProcessQueue.add(start);        Node current = null;        while((current = inProcess.poll())!= null){            int currentNodeWeight = current.getWeight();            if(current.equals(end)){                return current;            }else{                Set<Node> neighbors = getNeighbors(current,p,q,maze);                for(Node n:neighbors){                   if(!inProcessQueue.contains(n)){                      if(visited.containsKey(n)){                        Node visitedNode = visited.get(n);                        visited.remove(n);                        Node updatedNode = updatedNode(current,visitedNode);                        visited.put(updatedNode,updatedNode);                         }else{                        inProcess.add(n);                        inProcessQueue.add(n);                      }                  }                }                visited.put(current,current);            }        }        return null;    }    public static void main(String[] args){        boolean[][] maze = createMaze();        ShortestMazePath spm = new ShortestMazePath();        ShortestMazePath.Node startNode = spm.new Node(0,0,null,0);        ShortestMazePath.Node endNode = spm.new Node(2,1,null,0);        ShortestMazePath.Node pathNode = spm.findPath(maze,3,3,startNode,endNode);        while(pathNode != null){            System.out.println(Reached pathNode+pathNode);            pathNode = pathNode.getPrevious();        }           }}
Shortest path through a maze
java;graph;pathfinding;breadth first search
It looks like there is a bug in this piece of code:List<Node> neighbors = new ArrayList<Node>(){{             add(new Node(currentX-1,currentY,current,currentWeight));             add(new Node(currentX+1,currentY,current,currentWeight));             add(new Node(currentX,currentY+1,current,currentWeight));             add(new Node(currentX,currentY-1,current,currentWeight));}};The weight of the neighbors should be currentWeight + 1, not currentWeight(because we need one more step to reach the neighbor from the current node). And I would call it distance, not weight. The updatedNode method is redundant. Nodes are never updated in a breadth-first search. You can get rid of it.Map<Node,Node> visited = new HashMap<Node,Node>(); A map that maps a node to itself doesn't make much sense. I would use a Set<Node> here. And I do not see the point of having a Set inProcess. The entire algorithm is implemented in a pretty strange way. Here is pseudo code of a standard BFS implementation:discovered = an empty setqueue = an empty queuestartVetrex.dist = 0queue.add(startVertex)discovered.add(startVertex)while not queue.isEmpty():    v = queue.poll()    for neighbor <- neighbors(v):        if not discovered.contains(neighbor):            neighbor.dist = v.dist + 1            neighbor.parent = v            discovered.add(neighbor)            queue.add(neighbor)That's it. No need to update vertices or having several sets(visited, inQueue and so on).Whitespaces: there should be whitespaces around binary operators, before and after curly brackets, after the for, while and if keywords, between method parameters. For instance, private Set<Node> getNeighbors(Node current,int m,int n,boolean[][] maze){should beprivate Set<Node> getNeighbors(Node current, int m, int n, boolean[][] maze) {andwhile((current = inProcess.poll())!= null){should bewhile ((current = inProcess.poll()) != null) {Blank lines: it is conventional to have a blank line between methods, constructors and so on. Here is a refined part of your Node class:class Node {    private final int x;    private final int y;    private final int weight;    private final Node previous;    Node(int x, int y, Node previous, int weight) {        this.x = x;        this.y = y;        this.previous = previous;        this.weight = weight;    }    public int getX(){        return this.x;    }    public int getY(){        return this.y;    }    ...}You should also write documentation comments for all public classes and methods. 