BFS重建路径以获得最短路径

Question

我想从宽度优先搜索构建最短路径。我已经在Java代码中实现了BFS（如下所示），但是现在我不知道如何重建路径以获得实现代码的最短路径。

虽然我知道我必须保留一组父母，但我不知道把它放在我的代码中。基本上，我想从起点到目标点使用BFS追溯最短路径。请注意，我正在使用二维数组。

我做得对吗？有人可以帮助我吗？

public ArrayList<Point> shortestPath=new ArrayList<>(); 
public ArrayList<Point> BFS(Point start, Point end){ 
    int[][] distanceBoard=new int[50][50]; Point current,parent; 
    for(int i=0;i<distanceBoard.length;i++) 
     for(int j=0;j<distanceBoard.length;j++) distanceBoard[i][j]=Integer.MAX_VALUE; 
    distanceBoard[start.getX()][start.getY()]=0; 
    LinkedList<Point> q=new LinkedList<>(); 
    q.addFirst(start); 
    while(!q.isEmpty()){ 
     current=q.getFirst(); 
     if((new Point(current.getX(),current.getY()))==end) return shortestPath; 
     q.removeFirst(); 
     for(Point point:current.getNeighbours()){ 
      if(distanceBoard[point.getX()][point.getY()]==Integer.MAX_VALUE){ 
       distanceBoard[point.getX()][point.getY()]=distanceBoard[current.getX()][current.getY()]+1; 
       parent=current; 
       q.addLast(point); 
      } 
      shortestPath.add(current); 
     } 
    }return null; 
} 

Answer 1

原路返回，你可以只使用目标点的家长和继续下去，直到达到您开始的地方......像

ArrayList <vertex> points = new ArrayList < >(); 
while ((current.x != startx) || (current.y != starty)) { 
    points.add(current); 
    current = current.parent; 
} 

其中startx和starty是（X，Y ）你从你的网格开始的位置。你想在你找到你要寻找的目的地之后这么做，也就是在你跳出while(!q.isEmpty()){...}之后。

while (!q.isEmpty()) { 
    current = q.dequeue(); 
    if (current.x == targetx && current.y == targety) break; //quite when path is found 
    ... 
} 
ArrayList <vertex> vertices = new ArrayList < >(); 
while ((current.x != startx) || (current.y != starty)) { 
    vertices.add(current); 
    current = current.parent; 
} 

所以parentPoint是记住你来自哪里，因此，如果你有目标Point那么你应该有目的地Point的parent（或以前的位置）的方式，一旦你有目的地Point的parent你想找到目的地Point的parentparent等等，直到你有Point你开始搜索。我也只是为了增加你的困惑，在while ((current.x != startx)...)中犯了一个错误，所以不是while ((current.x != startx) && (current.y != starty))我将它改为while ((current.x != startx) || (current.y != start))，因为你不想停止迭代，比如你只有正确的y值，你想要它在双方都是假的时候停止，即当current.x != startx和current.y != start都是假的。