This is my first time implementing Dijkstra's algorithm. Okay so here I have a simple 2D 9 by 9 array:
Starting point is 1 and we're trying to get to any green square. Red squares are walls or lava (whatever satisfies your imagination).
How do I implement this in Java?
Computer science is not my field hence I'm not a seasoned programmer so I might not know how to do some stack pushing, only loops and recursion :( please keep it easy as possible and bear with me!
Here's something similiar that should get you started. However, the solution presented below attempts to get to the bottom right corner. You can relax that condition to find the bottom row. You will also need to change the encoding slightly to have a unique value that represents this row.
public class MazeSolver {
final static int TRIED = 2;
final static int PATH = 3;
// @formatter:off
private static int[][] GRID = {
{ 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1 },
{ 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};
// @formatter:off
public static void main(String[] args) {
MazeSolver maze = new MazeSolver(GRID);
boolean solved = maze.solve();
System.out.println("Solved: " + solved);
System.out.println(maze.toString());
}
private int[][] grid;
private int height;
private int width;
private int[][] map;
public MazeSolver(int[][] grid) {
this.grid = grid;
this.height = grid.length;
this.width = grid[0].length;
this.map = new int[height][width];
}
public boolean solve() {
return traverse(0,0);
}
private boolean traverse(int i, int j) {
if (!isValid(i,j)) {
return false;
}
if ( isEnd(i, j) ) {
map[i][j] = PATH;
return true;
} else {
map[i][j] = TRIED;
}
// North
if (traverse(i - 1, j)) {
map[i-1][j] = PATH;
return true;
}
// East
if (traverse(i, j + 1)) {
map[i][j + 1] = PATH;
return true;
}
// South
if (traverse(i + 1, j)) {
map[i + 1][j] = PATH;
return true;
}
// West
if (traverse(i, j - 1)) {
map[i][j - 1] = PATH;
return true;
}
return false;
}
private boolean isEnd(int i, int j) {
return i == height - 1 && j == width - 1;
}
private boolean isValid(int i, int j) {
if (inRange(i, j) && isOpen(i, j) && !isTried(i, j)) {
return true;
}
return false;
}
private boolean isOpen(int i, int j) {
return grid[i][j] == 1;
}
private boolean isTried(int i, int j) {
return map[i][j] == TRIED;
}
private boolean inRange(int i, int j) {
return inHeight(i) && inWidth(j);
}
private boolean inHeight(int i) {
return i >= 0 && i < height;
}
private boolean inWidth(int j) {
return j >= 0 && j < width;
}
public String toString() {
String s = "";
for (int[] row : map) {
s += Arrays.toString(row) + "\n";
}
return s;
}
}
I would suggest you start with writing down a method of applying dijkstras algorithm (assuming you know it in the first place) here in natural language and then start transforming it to your programming language.
The basic questions you will need to answer for that:
Once you did this you should be able to find a (probably not efficient) solution.
The optimal solution is indeed to use Dijkstra or AStar with a different finish condition. So you need to write if(targetNodes.contains(u)) break; instead of if(target == u) break;
(see wikipedia: If we are only interested in a shortest path between vertices source and target, we can terminate the search at line 13 if u = target.)
This is already implemented in my project called ... oh is this homework ;) ?
