如何使我的BFS算法运行得更快

Question

所以我有一个函数，它可以查看网格(2D数组(并找到从起点到终点的所有路径。到目前为止，算法按预期工作，我得到了我想要的值。

问题是这需要很长时间。它可以在100 x 100的网格上运行，没有问题，但一旦我到达10000 x 10000的网格，大约需要10分钟才能给出答案，我最多需要1分钟。

以下是它现在的样子：

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

再说一遍，虽然它有效，但它真的很慢。我正在尝试获取O(n + m)，但我相信它可能正在O(n^2)中运行。

有人知道让这更快的好主意吗？

Answer 1

观察到的低效率的一个明显原因是!validPaths.contains(tempPoint)和!queue.contains(tempPoint)的比较，它们都是O(n(。要进行这些比较，您应该努力实现O(1(比较，这可以通过使用特殊的数据结构(如哈希集或简单的位集(来实现。

现在，由于这些比较，您的实现显然是O(n^2(。