The first width search does not return the shortest path

Question

The first width search does not return the shortest path

I am trying to use a width search algorithm using Java. Given a 10x10 grid, I'm trying to find the last 9x9 cell (the grid starts at 0,0). By the time he reached 9x9, he had crossed all the cells in the grid. I heard BFS give me the shortest path. But actually it gave me the longest way.

Could you tell me if this is the expected behavior?
If so, how will BFS work, then what's the best way to get the shortest route to cell 9x9?

Please advice.

Edit-- I used this logic and completed my game. If you would like to contact, please check out https://play.google.com/store/apps/details?id=com.game.puzzle.game.ballmania.android

the code

package com.example.game.bfs.alogrithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFS {

static class Cell {
    private int x;
    private int y;
    private String value;
    private boolean visitStatus;

    public Cell(int x, int y, String value,boolean visitStatus) {
        this.x = x;
        this.y = y;
        this.value = value; 
        this.visitStatus=visitStatus;
    }
}

private Cell[][] board;

private List<Cell> visited = new ArrayList<Cell>();

private boolean testDone;

public void setBoard(Cell[][] board) {
    this.board = board;
} 

public Cell getAdjacentUnvisitedCell(Cell cell)
{  
   int moves[][] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
   for (int n = 0; n < 4 /* moves.length */; ++n) {
       int ti = cell.x + moves[n][0];
       int tj = cell.y + moves[n][1];
      // System.out.println("ti,tj" + ti +"," + tj );  

       if (ti >= 0 && ti < board.length && tj >= 0 && tj < board[0].length) { 

          // System.out.println("getAdjacentUnvisitedCell : " + "[" + board[ti][tj].x + "," + board[ti][tj].y + "]" ); 
          // System.out.println("getAdjacentUnvisitedCell : board[ti][tj].visitStatus " + board[ti][tj].visitStatus ); 

           if(!board[ti][tj].visitStatus) {  
              return board[ti][tj];
           }
       }
   }  
   return null;  
} 

public void BFSearch(Cell start, Cell end) {  
   // BFS uses Queue data structure 
   Queue<Cell> q = new LinkedList<Cell>(); 
   q.add(start);
   visited.add(start);
   board[start.x][start.y].visitStatus = true;

   //printNode(start);

   while( !q.isEmpty() )
   { 
      Cell c; 
      c = q.peek(); 
      Cell unVisitedadjCell = getAdjacentUnvisitedCell(c); 

      if(!testDone){
          testDone=true;  
      } 

      if ( unVisitedadjCell != null )
      {  visited.add(unVisitedadjCell); 
         board[unVisitedadjCell.x][unVisitedadjCell.y].visitStatus = true;

         printNode(unVisitedadjCell,c); 
         q.add(unVisitedadjCell);
      }
      else
      {
         q.remove();
      }
   }

   visited.clear();     //Clear visited property of nodes
}


private void printNode(Cell c,Cell node) {
    System.out.println("For Node " + node.x +"," + node.y + ",   " + "Just Visited : " + "[" + c.x + "," + c.y + "]" );  
} 

public static void main(String[] args) {
    Cell[][] cells = new Cell[10][10];
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cells[i][j] = new Cell(i, j, "defaultvalue",false);
        }
    } 

    BFS board = new BFS();
    board.setBoard(cells);

    board.BFSearch(cells[0][0], cells[1][4]);
}


}

}

Magazine:

For Node 0,0,   Just Visited : [1,0]
For Node 0,0,   Just Visited : [0,1]
For Node 1,0,   Just Visited : [2,0]
For Node 1,0,   Just Visited : [1,1]
For Node 0,1,   Just Visited : [0,2]
For Node 2,0,   Just Visited : [3,0]
For Node 2,0,   Just Visited : [2,1]
For Node 1,1,   Just Visited : [1,2]
For Node 0,2,   Just Visited : [0,3]
For Node 3,0,   Just Visited : [4,0]
For Node 3,0,   Just Visited : [3,1]
For Node 2,1,   Just Visited : [2,2]
For Node 1,2,   Just Visited : [1,3]
For Node 0,3,   Just Visited : [0,4]
For Node 4,0,   Just Visited : [5,0]
For Node 4,0,   Just Visited : [4,1]
For Node 3,1,   Just Visited : [3,2]
For Node 2,2,   Just Visited : [2,3]
For Node 1,3,   Just Visited : [1,4]
For Node 0,4,   Just Visited : [0,5]
For Node 5,0,   Just Visited : [6,0]
For Node 5,0,   Just Visited : [5,1]
For Node 4,1,   Just Visited : [4,2]
For Node 3,2,   Just Visited : [3,3]
For Node 2,3,   Just Visited : [2,4]
For Node 1,4,   Just Visited : [1,5]
For Node 0,5,   Just Visited : [0,6]
For Node 6,0,   Just Visited : [7,0]
For Node 6,0,   Just Visited : [6,1]
For Node 5,1,   Just Visited : [5,2]
For Node 4,2,   Just Visited : [4,3]
For Node 3,3,   Just Visited : [3,4]
For Node 2,4,   Just Visited : [2,5]
For Node 1,5,   Just Visited : [1,6]
For Node 0,6,   Just Visited : [0,7]
For Node 7,0,   Just Visited : [8,0]
For Node 7,0,   Just Visited : [7,1]
For Node 6,1,   Just Visited : [6,2]
For Node 5,2,   Just Visited : [5,3]
For Node 4,3,   Just Visited : [4,4]
For Node 3,4,   Just Visited : [3,5]
For Node 2,5,   Just Visited : [2,6]
For Node 1,6,   Just Visited : [1,7]
For Node 0,7,   Just Visited : [0,8]
For Node 8,0,   Just Visited : [9,0]
For Node 8,0,   Just Visited : [8,1]
For Node 7,1,   Just Visited : [7,2]
For Node 6,2,   Just Visited : [6,3]
For Node 5,3,   Just Visited : [5,4]
For Node 4,4,   Just Visited : [4,5]
For Node 3,5,   Just Visited : [3,6]
For Node 2,6,   Just Visited : [2,7]
For Node 1,7,   Just Visited : [1,8]
For Node 0,8,   Just Visited : [0,9]
For Node 9,0,   Just Visited : [9,1]
For Node 8,1,   Just Visited : [8,2]
For Node 7,2,   Just Visited : [7,3]
For Node 6,3,   Just Visited : [6,4]
For Node 5,4,   Just Visited : [5,5]
For Node 4,5,   Just Visited : [4,6]
For Node 3,6,   Just Visited : [3,7]
For Node 2,7,   Just Visited : [2,8]
For Node 1,8,   Just Visited : [1,9]
For Node 9,1,   Just Visited : [9,2]
For Node 8,2,   Just Visited : [8,3]
For Node 7,3,   Just Visited : [7,4]
For Node 6,4,   Just Visited : [6,5]
For Node 5,5,   Just Visited : [5,6]
For Node 4,6,   Just Visited : [4,7]
For Node 3,7,   Just Visited : [3,8]
For Node 2,8,   Just Visited : [2,9]
For Node 9,2,   Just Visited : [9,3]
For Node 8,3,   Just Visited : [8,4]
For Node 7,4,   Just Visited : [7,5]
For Node 6,5,   Just Visited : [6,6]
For Node 5,6,   Just Visited : [5,7]
For Node 4,7,   Just Visited : [4,8]
For Node 3,8,   Just Visited : [3,9]
For Node 9,3,   Just Visited : [9,4]
For Node 8,4,   Just Visited : [8,5]
For Node 7,5,   Just Visited : [7,6]
For Node 6,6,   Just Visited : [6,7]
For Node 5,7,   Just Visited : [5,8]
For Node 4,8,   Just Visited : [4,9]
For Node 9,4,   Just Visited : [9,5]
For Node 8,5,   Just Visited : [8,6]
For Node 7,6,   Just Visited : [7,7]
For Node 6,7,   Just Visited : [6,8]
For Node 5,8,   Just Visited : [5,9]
For Node 9,5,   Just Visited : [9,6]
For Node 8,6,   Just Visited : [8,7]
For Node 7,7,   Just Visited : [7,8]
For Node 6,8,   Just Visited : [6,9]
For Node 9,6,   Just Visited : [9,7]
For Node 8,7,   Just Visited : [8,8]
For Node 7,8,   Just Visited : [7,9]
For Node 9,7,   Just Visited : [9,8]
For Node 8,8,   Just Visited : [8,9]
For Node 9,8,   Just Visited : [9,9]

, .

+4

java breadth-first-search depth-first-search a-star

iappmaker 04 . '15 17:40

2

, ( lared), :

package com.example.game.bfs.alogrithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


/**
   http://stackoverflow.com/questions/27768394/breadth-first-search-is-not-returning-the-shortest-path
 **/
public class BFS {

static class Cell {
    private int x;
    private int y;
    private String value;
    private boolean visitStatus;
    private Cell previousCell;

    public Cell(int x, int y, String value,boolean visitStatus) {
        this.x = x;
        this.y = y;
        this.value = value; 
        this.visitStatus=visitStatus;
    }

    public String toString()
    {
    return  "[" +   x + "," +   y + "]";
    }
}

private Cell[][] board;

private List<Cell> visited = new ArrayList<Cell>();

private boolean testDone;

public void setBoard(Cell[][] board) {
    this.board = board;
} 

public Cell getAdjacentUnvisitedCell(Cell cell)
{  
    int moves[][] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
    // for diagonal moves :
    // int moves[][] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 }, {1,1} };
   for (int n = 0; n < moves.length ; ++n) {
       int ti = cell.x + moves[n][0];
       int tj = cell.y + moves[n][1];
      // System.out.println("ti,tj" + ti +"," + tj );  

       if (ti >= 0 && ti < board.length && tj >= 0 && tj < board[0].length) { 

          // System.out.println("getAdjacentUnvisitedCell : " + "[" + board[ti][tj].x + "," + board[ti][tj].y + "]" ); 
          // System.out.println("getAdjacentUnvisitedCell : board[ti][tj].visitStatus " + board[ti][tj].visitStatus ); 

           if(!board[ti][tj].visitStatus) {  
              return board[ti][tj];
           }
       }
   }  
   return null;  
} 

public void BFSearch(Cell start, Cell end) {  
   // BFS uses Queue data structure 
   Queue<Cell> q = new LinkedList<Cell>(); 
   Cell unVisitedadjCell = start; 
   Cell c =  null;
   q.add(start);
   visited.add(start);
   board[start.x][start.y].visitStatus = true;

   //printNode(start);

   while( !q.isEmpty() )
   { 
      c = q.peek(); 
      unVisitedadjCell = getAdjacentUnvisitedCell(c); 

      if(!testDone){
          testDone=true;  
      } 

      if ( unVisitedadjCell != null )
      {  visited.add(unVisitedadjCell); 
         board[unVisitedadjCell.x][unVisitedadjCell.y].visitStatus = true;

         printNode(unVisitedadjCell,c);
         unVisitedadjCell.previousCell=c; 
         q.add(unVisitedadjCell);
      }
      else
      {
         q.remove();
      }
   }
   System.out.println("Shortest path");

   while ( ( c != null ) && ( c!=start))
       {
       printNode(c.previousCell,c);
       c = c.previousCell;
       }

   visited.clear();     //Clear visited property of nodes
}


private void printNode(Cell c,Cell node) {
    System.out.println("For Node " + node.x +"," + node.y + ",  " + "Just Visited : " + c + " previous was " + node.previousCell);
} 

public static void main(String[] args) {
    Cell[][] cells = new Cell[10][10];
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cells[i][j] = new Cell(i, j, "defaultvalue",false);
        }
    }
    cells[0][1].value = "B";
    cells[0][2].value = "B";
    cells[1][1].value = "B";
    cells[1][3].value = "B";
    cells[2][1].value = "B";
    cells[2][2].value = "B";
    cells[2][3].value = "B";
    cells[2][7].value = "B";
    cells[2][8].value = "B"; 

    BFS board = new BFS();
    board.setBoard(cells);

    board.BFSearch(cells[0][0], cells[1][4]);
}


}

java -cp. com.example.game.bfs.alogrithm.BFS

For Node 0,0,  Just Visited : [1,0] previous was null
For Node 0,0,  Just Visited : [0,1] previous was null
For Node 1,0,  Just Visited : [2,0] previous was [0,0]
For Node 1,0,  Just Visited : [1,1] previous was [0,0]
For Node 0,1,  Just Visited : [0,2] previous was [0,0]
For Node 2,0,  Just Visited : [3,0] previous was [1,0]
For Node 2,0,  Just Visited : [2,1] previous was [1,0]
For Node 1,1,  Just Visited : [1,2] previous was [1,0]
For Node 0,2,  Just Visited : [0,3] previous was [0,1]
For Node 3,0,  Just Visited : [4,0] previous was [2,0]
For Node 3,0,  Just Visited : [3,1] previous was [2,0]
For Node 2,1,  Just Visited : [2,2] previous was [2,0]
For Node 1,2,  Just Visited : [1,3] previous was [1,1]
For Node 0,3,  Just Visited : [0,4] previous was [0,2]
For Node 4,0,  Just Visited : [5,0] previous was [3,0]
For Node 4,0,  Just Visited : [4,1] previous was [3,0]
For Node 3,1,  Just Visited : [3,2] previous was [3,0]
For Node 2,2,  Just Visited : [2,3] previous was [2,1]
For Node 1,3,  Just Visited : [1,4] previous was [1,2]
For Node 0,4,  Just Visited : [0,5] previous was [0,3]
For Node 5,0,  Just Visited : [6,0] previous was [4,0]
For Node 5,0,  Just Visited : [5,1] previous was [4,0]
For Node 4,1,  Just Visited : [4,2] previous was [4,0]
For Node 3,2,  Just Visited : [3,3] previous was [3,1]
For Node 2,3,  Just Visited : [2,4] previous was [2,2]
For Node 1,4,  Just Visited : [1,5] previous was [1,3]
For Node 0,5,  Just Visited : [0,6] previous was [0,4]
For Node 6,0,  Just Visited : [7,0] previous was [5,0]
For Node 6,0,  Just Visited : [6,1] previous was [5,0]
For Node 5,1,  Just Visited : [5,2] previous was [5,0]
For Node 4,2,  Just Visited : [4,3] previous was [4,1]
For Node 3,3,  Just Visited : [3,4] previous was [3,2]
For Node 2,4,  Just Visited : [2,5] previous was [2,3]
For Node 1,5,  Just Visited : [1,6] previous was [1,4]
For Node 0,6,  Just Visited : [0,7] previous was [0,5]
For Node 7,0,  Just Visited : [8,0] previous was [6,0]
For Node 7,0,  Just Visited : [7,1] previous was [6,0]
For Node 6,1,  Just Visited : [6,2] previous was [6,0]
For Node 5,2,  Just Visited : [5,3] previous was [5,1]
For Node 4,3,  Just Visited : [4,4] previous was [4,2]
For Node 3,4,  Just Visited : [3,5] previous was [3,3]
For Node 2,5,  Just Visited : [2,6] previous was [2,4]
For Node 1,6,  Just Visited : [1,7] previous was [1,5]
For Node 0,7,  Just Visited : [0,8] previous was [0,6]
For Node 8,0,  Just Visited : [9,0] previous was [7,0]
For Node 8,0,  Just Visited : [8,1] previous was [7,0]
For Node 7,1,  Just Visited : [7,2] previous was [7,0]
For Node 6,2,  Just Visited : [6,3] previous was [6,1]
For Node 5,3,  Just Visited : [5,4] previous was [5,2]
For Node 4,4,  Just Visited : [4,5] previous was [4,3]
For Node 3,5,  Just Visited : [3,6] previous was [3,4]
For Node 2,6,  Just Visited : [2,7] previous was [2,5]
For Node 1,7,  Just Visited : [1,8] previous was [1,6]
For Node 0,8,  Just Visited : [0,9] previous was [0,7]
For Node 9,0,  Just Visited : [9,1] previous was [8,0]
For Node 8,1,  Just Visited : [8,2] previous was [8,0]
For Node 7,2,  Just Visited : [7,3] previous was [7,1]
For Node 6,3,  Just Visited : [6,4] previous was [6,2]
For Node 5,4,  Just Visited : [5,5] previous was [5,3]
For Node 4,5,  Just Visited : [4,6] previous was [4,4]
For Node 3,6,  Just Visited : [3,7] previous was [3,5]
For Node 2,7,  Just Visited : [2,8] previous was [2,6]
For Node 1,8,  Just Visited : [1,9] previous was [1,7]
For Node 9,1,  Just Visited : [9,2] previous was [9,0]
For Node 8,2,  Just Visited : [8,3] previous was [8,1]
For Node 7,3,  Just Visited : [7,4] previous was [7,2]
For Node 6,4,  Just Visited : [6,5] previous was [6,3]
For Node 5,5,  Just Visited : [5,6] previous was [5,4]
For Node 4,6,  Just Visited : [4,7] previous was [4,5]
For Node 3,7,  Just Visited : [3,8] previous was [3,6]
For Node 2,8,  Just Visited : [2,9] previous was [2,7]
For Node 9,2,  Just Visited : [9,3] previous was [9,1]
For Node 8,3,  Just Visited : [8,4] previous was [8,2]
For Node 7,4,  Just Visited : [7,5] previous was [7,3]
For Node 6,5,  Just Visited : [6,6] previous was [6,4]
For Node 5,6,  Just Visited : [5,7] previous was [5,5]
For Node 4,7,  Just Visited : [4,8] previous was [4,6]
For Node 3,8,  Just Visited : [3,9] previous was [3,7]
For Node 9,3,  Just Visited : [9,4] previous was [9,2]
For Node 8,4,  Just Visited : [8,5] previous was [8,3]
For Node 7,5,  Just Visited : [7,6] previous was [7,4]
For Node 6,6,  Just Visited : [6,7] previous was [6,5]
For Node 5,7,  Just Visited : [5,8] previous was [5,6]
For Node 4,8,  Just Visited : [4,9] previous was [4,7]
For Node 9,4,  Just Visited : [9,5] previous was [9,3]
For Node 8,5,  Just Visited : [8,6] previous was [8,4]
For Node 7,6,  Just Visited : [7,7] previous was [7,5]
For Node 6,7,  Just Visited : [6,8] previous was [6,6]
For Node 5,8,  Just Visited : [5,9] previous was [5,7]
For Node 9,5,  Just Visited : [9,6] previous was [9,4]
For Node 8,6,  Just Visited : [8,7] previous was [8,5]
For Node 7,7,  Just Visited : [7,8] previous was [7,6]
For Node 6,8,  Just Visited : [6,9] previous was [6,7]
For Node 9,6,  Just Visited : [9,7] previous was [9,5]
For Node 8,7,  Just Visited : [8,8] previous was [8,6]
For Node 7,8,  Just Visited : [7,9] previous was [7,7]
For Node 9,7,  Just Visited : [9,8] previous was [9,6]
For Node 8,8,  Just Visited : [8,9] previous was [8,7]
For Node 9,8,  Just Visited : [9,9] previous was [9,7]
Shortest path
For Node 9,9,  Just Visited : [9,8] previous was [9,8]
For Node 9,8,  Just Visited : [9,7] previous was [9,7]
For Node 9,7,  Just Visited : [9,6] previous was [9,6]
For Node 9,6,  Just Visited : [9,5] previous was [9,5]
For Node 9,5,  Just Visited : [9,4] previous was [9,4]
For Node 9,4,  Just Visited : [9,3] previous was [9,3]
For Node 9,3,  Just Visited : [9,2] previous was [9,2]
For Node 9,2,  Just Visited : [9,1] previous was [9,1]
For Node 9,1,  Just Visited : [9,0] previous was [9,0]
For Node 9,0,  Just Visited : [8,0] previous was [8,0]
For Node 8,0,  Just Visited : [7,0] previous was [7,0]
For Node 7,0,  Just Visited : [6,0] previous was [6,0]
For Node 6,0,  Just Visited : [5,0] previous was [5,0]
For Node 5,0,  Just Visited : [4,0] previous was [4,0]
For Node 4,0,  Just Visited : [3,0] previous was [3,0]
For Node 3,0,  Just Visited : [2,0] previous was [2,0]
For Node 2,0,  Just Visited : [1,0] previous was [1,0]
For Node 1,0,  Just Visited : [0,0] previous was [0,0]

...

+1

philippe lhardy 04 . '15 19:38

lared · Accepted Answer · 2015-01-04T18:08:39+0000

, . , - . , , ( BFS , ), , "" "", .

- 0 9, 9 . 2 , (0, 0) (9, 9), 1 1, 9+9=18. , 18 . , , to the right down, 18 , , , . , , - , . .

edit: , . , 18 ; 9 to the right 9 down. , (9, 9) (0, 0), . ? : a_1, a_2, ... a_18. 9 down. , down, 18 ( 18 ), (17 ) , down . 18*17*...*10 . right. ( ) 9*8*...*1. down, ? down 9, 8 . right. , , (18*17*...*1)/((9*8*...*1)*(9*8*...*1)) = 48 620 ( ). 9 18 .

, Introductory combinatorics Richard A. Brualdi. . .

The first width search does not return the shortest path

the code

Magazine:

More articles: