public static void main(String[] args) {

int[][] grid = new int[][]{

{1, 3, 1},

{1, 5, 1},

{4, 2, 1}

};

// result 7

DijkstraPathSum(grid);

minPahtSum(grid);

int[][] a2 = new int[][]{{3}};

//3

DijkstraPathSum(a2);

minPahtSum(a2);

int[][] a3 = new int[][]{

{1, 0, 4, 9, 6, 0, 9, 1, 8, 9, 5},

{1, 2, 8, 9, 2, 4, 8, 1, 7, 3, 2},

{5, 0, 7, 9, 3, 5, 1, 3, 8, 2, 3},

{3, 2, 2, 5, 3, 3, 3, 2, 0, 5, 6},

{9, 6, 8, 3, 6, 2, 0, 1, 4, 6, 1},

{1, 7, 4, 8, 8, 9, 7, 1, 3, 2, 5},

{7, 7, 8, 0, 3, 0, 0, 0, 8, 1, 8},

{8, 7, 4, 0, 9, 5, 4, 7, 9, 8, 5},

{5, 6, 3, 5, 5, 6, 0, 7, 1, 7, 7},

{9, 9, 2, 1, 1, 2, 1, 5, 0, 0, 4}

};

//40

DijkstraPathSum(a3);

minPahtSum(a3);

}

// only left or down, Dynamic programming to solve this.

public static void minPahtSum(int[][] grid) {

if (grid.length == 0) {

System.out.println("sum path for zero grid " + 0);

return;

}

int row = grid.length;

int col = grid[0].length;

// calculate left edge

for (int i = row - 1; i > 0; --i)

grid[i - 1][col - 1] += grid[i][col - 1];

// calculate bottom edge

for (int j = col - 1; j > 0; --j)

grid[row - 1][j - 1] += grid[row - 1][j];

for (int i = row - 2; i >= 0; --i) {

for (int j = col - 2; j >= 0; --j) {

//sum with the less one

grid[i][j] +=

(grid[i + 1][j] < grid[i][j + 1]) ?

grid[i + 1][j] : grid[i][j + 1];

}

}

System.out.println(grid[0][0]);

}

// Dijkstra's algorithm

public static void DijkstraPathSum(int[][] grid) {

if (grid.length == 0) {

System.out.println("sum path for zero grid " + 0);

return;

}

int row = grid.length;

int col = grid[0].length;

boolean[][] visit = new boolean[row][col];

int[][] cost = new int[row][col];

for (int i = 0; i < row; i++) {

for (int j = 0; j < col; j++) {

cost[i][j] = Integer.MAX_VALUE;

}

}

String[][] path = new String[row][col];

cost[0][0] = grid[0][0];

path[0][0] = "0-0";

visit[0][0] = true;

for (int i = 0; i < row; i++) {

for (int j = 0; j < col && visit[i][j]; j++) {

//left

int r = i + 1, c = j;

if (r < row) {

if (cost[r][c] > cost[i][j] + grid[r][c]) {

cost[r][c] = cost[i][j] + grid[r][c];

visit[r][c] = true;

path[r][c] = String.valueOf(i) + "-" + String.valueOf(j);

}

}

// down

r = i;

c = j + 1;

if (c < col) {

if (cost[r][c] > cost[i][j] + grid[r][c]) {

cost[r][c] = cost[i][j] + grid[r][c];

visit[r][c] = true;

path[r][c] = String.valueOf(i) + "-" + String.valueOf(j);

}

}

}

}

System.out.println(cost[row - 1][col - 1]);

// System.out.println(Arrays.deepToString(cost));

}