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都是假的。