BFS最短経路を得るために経路を再構築

Question

私は幅優先探索から最短経路を構築したいと考えています。私はJavaコードでBFSを実装しましたが（下図参照）、コードの実装から最短パスを得るためにパスを再構築する方法はわかりません。

私は親の配列を保持しなければならないことは分かっていますが、私はどこにコードを入れるべきかわかりません。基本的には、スタートポイントからゴールポイントまでのBFSを使用して最短パスをトレースしたいと思います。私は2D配列を使用していることに注意してください。

正しくしていますか？誰かが私を助けてくれますか？

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のparentPointのparentparentなどを検索したい場合は、Pointで検索を開始します。また、あなたの混乱に追加するだけで、に間違いがありました。while ((current.x != startx) && (current.y != starty))私はそれをwhile ((current.x != startx) || (current.y != start))に変更しました。たとえば、正しいy値しか持っていないときに反復を止めたくない場合は、両側が偽であるとき、すなわちcurrent.x != startxとcurrent.y != startの両方が偽であるときに停止する。