Problem
Given a size MxN positive integer array, find the smallest path summary from arr[0][0] to arr[m-1][n-1].We can model this problem as an edge weighted digraph, then use dijkstra's algorithm to solve it. Each array index (i,j) is a node, each node has two outward edges, one edge points to the node at right, another edge points to the node below. The leaving edges' weight are arr[i][j]. Using dijkstra's algorthm here is a little bit overkill. Let's use dynamic programming to solve this problem instead.
Assuming we already found the shortest path f(i,j) from arr[0][0] to arr[i][j], f(i,j) must satisfy:
f(i, j) = min(f(i - 1, j), f(i, j - 1)) + a[i][j]. We can start from arr[0][0] and initial conditions f(i,0) = arr[0][0] + arr[1][0] + ... + arr[i][0] and f(0, j) = a[0][0] + a[0][1] + ... + a[0][j], then fill up all the shortest path for each index (i, j) with the formula. The value of f(m -1, n-1) is the answer to this question.
public class ShortestPathIn2DArray {
public static int getMinPath(int[][] arr) {
if(arr == null || arr.length == 0)
return 0;
int row = arr.length;
int col = arr[0].length;
int[][] cache = new int[row][col];
cache[0][0] = arr[0][0];
for(int i = 1; i < col; i++) {
cache[0][i] = cache[0][i-1] + arr[0][i];
}
for(int j = 1; j < row; j++) {
cache[j][0] = cache[j-1][0] + arr[j][0];
}
for(int i=1; i<row; i++) {
for(int j=1; j<col; j++) {
System.out.println("cache[" + (i-1) + "][" + j + "] = " + cache[i-1][j] + " cache[" + i + "][" + (j-1) + "]=" + cache[i][j-1]);
if(cache[i-1][j] > cache[i][j-1]) {
cache[i][j] = cache[i][j-1] + arr[i][j];
System.out.println("[" + i + "," + (j-1) + "] =" + arr[i][j-1]);
} else {
cache[i][j] = cache[i-1][j] + arr[i][j];
System.out.println("[" + (i-1) + "," + j + "] =" + arr[i-1][j]);
}
System.out.println("cache[" + i + "][" + j + "] = " + cache[i][j]);
}
}
System.out.println("[" + (row -1) + "," + (col - 1) + "] =" + arr[row-1][col-1]);
return cache[row-1][col-1];
}
public static void main(String...args) {
int[][] arr = {
{1, 4, 3},
{8, 7, 5},
{2, 1, 5}
};
System.out.println(getMinPath(arr));
int row = arr.length;
int col = arr[0].length;
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
System.out.print(arr[i][j] + ", ");
}
System.out.println();
}
}
}
The problem can also be solved by tracing back from destination to source.
In the above example, we can find the shortest distance at the cache[row - 1][col - 1], however, we can not provide the path. In order to provide the path, bfs map traversal is needed.
Let's first take a look at a related but simpler version of the above problem.
Problem
Given a size NxN maze, value 1 present a path, value 0 means no path. You need to walk from [0][0] to [N-1][N-1]. Only right move and down move is allowed. Find such a path. For example: given the following 2D array
{
{1, 1, 0, 0},
{1, 0, 1, 0},
{1, 1, 1, 0},
{0, 0, 1, 1}
}
the output should be
1 0 0 0
1 0 0 0
1 1 1 0
0 0 1 1
Solution
If we just have to answer if the path exists, we can iterate the whole 2D array, use union find to connect all the adjacent neighbors, then we call isConnected(0-0, 3-3). However, if we need to find the path, we can model it as an undirected map, then do a dfs traversal in order to find a path from s = 0-0 to s = 3-3. Using graph here is kind of overkill. We can use traceback instead.
The rational is as following:
Assuming we moved into (i, j), we need to make decision to move to (i + 1, j) or (i, j + 1) next. We can pick (i + 1, j) first, then recursively move right or down until we reached (N-1, N-1). If picking (i + 1, j) turns out to be a mistake, we picks (i, j + 1) instead. If both choices are wrong, we return to the caller, moving to (i, j) is a mistake, so that the caller can try another option.
The java code realizing the above algorithm is as follows:
public class Maze {
final int N = 4;
private void printSolution(int[][] sol) {
for(int i = 0; i < sol.length; i++) {
for(int j = 0; j < sol[i].length; j++) {
System.out.print(sol[i][j] + " ");
}
System.out.println();
}
}
boolean isSafe(int[][] maze, int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1;
}
private boolean getPath(int[][] maze, int x, int y, int[][] sol) {
if(x == N-1 && y == N-1) {
sol[x][y] = 1;
return true;
}
if(isSafe(maze, x, y)) {
sol[x][y] = 1;
if(getPath(maze, x + 1, y, sol))
return true;
if(getPath(maze, x, y+ 1, sol))
return true;
sol[x][y] = 0;
}
return false;
}
public static void main(String...args) {
Maze m = new Maze();
int maze[][] = new int[][]{
{1, 1, 0, 0},
{1, 0, 1, 0},
{1, 1, 1, 0},
{0, 0, 1, 1}
};
int sol[][] = new int[][] {
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if(m.getPath(maze, 0, 0, sol)) {
m.printSolution(sol);
} else {
System.out.println("no path exists");
}
}
}
This approach has similar stack trace as dfs map traversal, on average, graph dfs traversl has O(V + E), here the V = N^2 and E depends on how many 1s in the maze. The time complexity is bounded by O(N^2 + E), the space complexity is bound by the sol[][] which is O(N^2) as well.
