Get the least weight path from the matrix recursively

Question

let's say I have a matrix n ^ n . There is a positive number in each cell, and I need to get the path with the smallest weight .

a path is every path starting in matrix[0][0] and ending in matrix[matrix.length-1][matrix[0].length-1] , without diagonals.

path weight is the number of all numbers in it.

For example, suppose I have this matrix:

 mat = {{1,2},{3,4}}; 

therefore, {1,2,4} is the path , and {1,3,4} is another path .

The weight of the first path is 7 (1 + 2 + 4), and the second has a weight of 8 (1 + 3 + 4), so the function will return 7 .

I need to solve it recursively. The pseudocode should look something like this:

 if i > matrix.length-1 || i < 0 || j > matrix[0].length-1 || j < 0 //then I passed the borders, so I need to step back. if i == matrix.length-1 && j == matrix[0].length-1 //Then I reached the last cell, and I need to retrieve sum 

Then call four recursive calls:

 public static int smallPath(a, i+1, j, sum); public static int smallPath(a, i, j+1, sum); public static int smallPath(a, i-1, j, sum); public static int smallPath(a, i, j-1, sum); 

Then I need to get something, what?

I know this is not relevant, but what is the general idea, can someone help me solve this? Thanks!

Answer 1

I'm not sure if this is the most effective solution, but you should think about it:

• First you need to check the random path first and get its sum .
• Systematically. Try another one, and if its amount is more in progress, stop it and try another.
• If you find the smallest sum method, write down its sum (and directions) and try another one until there is no way
• You have a result :)

This solution will work for direct paths. I mean, you always take a step to the right or right. Do not return (up or left) - if you start from the upper left cell and end in the lower right corner.

Check the difference:

The first is obvious, the smallest amount is 18 (3 + 2 + 1 + 0 + 1 + 2 + 4 + 3 + 2) .., but in the second the result corresponds to my direct method 107 and not 17 as the correct solution.

As a rule, to find the best solution in this case is very difficult, and you need to indicate whether any restrictions are set or not.

Answer 2

You should be able to use the Digestra algorithm, where the nodes are "between" the matrix cells, and the connections are implied by cell weights.

A detailed answer can be found on this question: Javascript: Pathfinding in the (50000 * 50000) 2d grid?