How can I make my BFS algorithm run faster?

Question

So I have a function that looks at a grid (2D array) and finds all the paths from the starting point to the end point. So far the algorithm works as intended and I get the values that I'm looking for.

The problem is that it takes forever. It can run over a 100 x 100 grid no problem, but once I get to a 10000 x 10000 grid, it'll take about 10 min to give back an answer, where I'm looking for maybe 1 min at most.

Here's what it looks like right now:

public void BFS(Point s, Point e){
        /**
         * North, South, East, West coordinates
         */
        int[] x = {0,0,1,-1};
        int[] y = {1,-1,0,0};

        LinkedList<Point> queue = new LinkedList<>();
        queue.add(s);

        /**
         * 2D int[][] grid that stores the distances of each point on the grid
         * from the start
         */
        int[][] dist = new int[numRow][numCol];
        for(int[] a : dist){
            Arrays.fill(a,-1);
        }
        /**
        * "obstacles" is an array of Points that contain the (x, y) coordinates of obstacles on the grid
        * designated as a -2, which the BFS algorithm will avoid.
        */
        for(Point ob : obstacles){
            dist[ob.x][ob.y] = -2;
        }
        // Start point
        dist[s.x][s.y] = 0;

        /**
         * Loops over dist[][] from starting point, changing each [x][y] coordinate to the int
         * value that is the distance from S.
         */
        while(!queue.isEmpty()){                                        
            Point p = queue.removeFirst();
            for(int i = 0; i < 4; i++){                             
                int a = p.x + x[i];
                int b = p.y + y[i];
                if(a >= 0 && b >= 0 && a < numRow && b < numCol && dist[a][b] == -1){
                    dist[a][b] = 1 + dist[p.x][p.y];
                    Point tempPoint = new Point(a, b);
                    if(!queue.contains(tempPoint)){
                        queue.add(tempPoint);
                    }
                }
            }
        }

        /**
         * Works backwards to find all shortest path points between S and E, and adds each
         * point to an array called "validPaths"
         */
        queue.add(e);
        while(!queue.isEmpty()){
            Point p = queue.removeFirst();

            // Checks grid space (above, below, left, and right) from Point p
            for(int i = 0; i < 4; i++){
                int curX = p.x + x[i];
                int curY = p.y + y[i];

                // Index Out of Bounds check
                if(curX >= 0 && curY >= 0 && !(curX == start.x && curY == start.y) && curX < numRow && curY < numCol){
                    if(dist[curX][curY] < dist[p.x][p.y] && dist[curX][curY] != -2){ // -2 is an obstacle
                        Point tempPoint = new Point(curX, curY);
                        if(!validPaths.contains(tempPoint)){
                            validPaths.add(tempPoint);
                        }
                        if(!queue.contains(tempPoint)){
                            queue.add(tempPoint);
                        }
                    }
                }
            }
        }

So again, while it works, it's really slow. I'm trying to get a O(n + m), but I believe that it might be running in O(n^2).

Does anyone know any good ideas to make this faster?

Answer 1

An clear reason for the observed inefficiency are the comparisons !validPaths.contains(tempPoint) and !queue.contains(tempPoint) which are both O(n). To do these comparisons you should be striving for an O(1) comparison, which can be accomplished by using a special datastructure such as a hash-set or simply a bitset.

As it stands now, your implementation is clearly O(n^2) because of these comparisons.