BFS algorithm in grids/mazes

[mirhagk]

If the edge sizes are the same then Dijkstra is the exact same as BFS. If A* has a heuristic of 0 (ie you don't have a way to estimate how close you are) then it's the same as Dijkstra.

Because of the above 2 properties neither A* nor Dijkstra helps any with the example I've been using. We can't guess how far away we are from the end because we don't know where the end is. Therefore our A* is Dijkstra. Every movement we make is the same distance (it takes just as long to go left as it does to go right etc). That means that every edge size is the same, so any Dijkstra would just be BFS.

[Panphobia]

So if dijkstra just be BFS would it execute any faster? If not which algorithm would execute faster, and is lee's algorithm good?

[mirhagk]

since the algorithms operate equivalently, the simplest one would be the fastest, so BFS would be the fastest.

Lee's algorithm looks interesting, but it just looks like a different (maybe more inefficient) way to do BFS. I don't really see a difference in the algorithm itself, but I don't know (I'm just going off of the wikipedia page)

[Panphobia]

thing is, the BFS runs in 4-5 seconds when it needs to be < 2.5s, soooo which algorithm would you recommend

[mirhagk]

what is the exact problem?

[Panphobia]

So here is my code for a bfs from A to B in a grid,I checked some other code and edited it to fit mine, is it alright, and is it efficient enough?

code:

package bfs; import java.util.*; import java.io.*; public class BFS {     public static void main(String[] args) {         int c = 0;         String text = "A........."                 + "##....##.."                 + ".####...##"                 + ".........."                 + ".......###"                 + ".....#...."                 + "####...###"                 + "B........."                 + "#...#.###."                 + "..........";         char[][] maze = new char[10][10];         for (int x = 0; x < 10; x++) {             for (int y = 0; y < 10; y++) {                 maze[x][y] = text.charAt(c);                 c += 1;             }         }         System.out.println(bfs(maze, 0, 0, '#'));     }     public static int bfs(char[][] maze, int x, int y, char wall) {         Queue<int[]> queue = new LinkedList<int[]>();         int[] start = {y, x, 0};         queue.add(start);         while (queue.peek() != null) {             int[] array = queue.remove();             if (array[0] - 1 > -1 && maze[array[0] - 1][array[1]] != wall) {                 if (maze[array[0] - 1][array[1]] == 'B') {                     return array[2] + 1;                 } else {                     maze[array[0] - 1][array[1]] = wall;                     int[] temp = {array[0] - 1, array[1], array[2] + 1};                     queue.add(temp);                 }             }             if (array[1] - 1 > -1 && maze[array[0]][array[1] - 1] != wall) {                 if (maze[array[0]][array[1] - 1] == 'B') {                     return array[2] + 1;                 } else {                     maze[array[0]][array[1] - 1] = wall;                     int[] temp = {array[0], array[1] - 1, array[2] + 1};                     queue.add(temp);                 }             }             if (array[1] + 1 < 10 && maze[array[0]][array[1] + 1] != wall) {                 if (maze[array[0]][array[1] + 1] == 'B') {                     return array[2] + 1;                 } else {                     maze[array[0]][array[1] + 1] = wall;                     int[] temp = {array[0], array[1] + 1, array[2] + 1};                     queue.add(temp);                 }             }             if (array[0] + 1 < 10 && maze[array[0] + 1][array[1]] != wall) {                 if (maze[array[0] + 1][array[1]] == 'B') {                     return array[2] + 1;                 } else {                     maze[array[0] + 1][array[1]] = wall;                     int[] temp = {array[0] + 1, array[1], array[2] + 1};                     queue.add(temp);                 }             }         }         return 0;     } }