BFS реконструирует путь, чтобы получить кратчайший путь

Я хотел бы построить кратчайший путь от широты первого поиска. Я реализовал BFS в коде Java (как показано ниже), но теперь я не знаю, как восстановить путь, чтобы получить кратчайший путь от реализации кода.

Хотя я знаю, что я должен держать массив родителей, я не знаю, где положить его в моем коде. В принципе, я хотел бы проследить самый короткий путь с помощью 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;
}

1 ответ

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

    Таким parent Pointобразом, это способ запоминания, откуда вы пришли, и поэтому, если у вас есть пункт назначенияPoint, то вы должны иметь пункт назначения Pointparent(или предыдущую позицию), и как только у вас есть пункт назначенияPointparent, вы хотите найти пункт назначения Pointparent parentи так далее, пока у вас не будет Pointвы начали поиск. Я тоже, просто, чтобы добавить к вашей путаницы, ошиблись в while ((current.x != startx)...) так вместо того, что это while ((current.x != startx) && (current.y != starty)) я изменила ему while ((current.x != startx) || (current.y != start)) , поскольку вы не хотите, чтобы остановить итерации, когда например у вас есть только правильное значение, вы хотите его остановить, когда обе стороны являются ложными, т. е. когда оба current.x != startx и current.y != start являются ложными.