CODEWITHSUNDEEP
javaalgorithmrecursionmatrix
Avishay28
Avishay28

Reputation: 2456

retrieve the path with the lowest weight from matrix recursively

let's say I have a n^n matrix. In every cell there is a positive number, and I need to retrieve the path with the lowest weight.

path is every path that start in matrix[0][0] and end in matrix[matrix.length-1][matrix[0].length-1], without diagonals.

weight of a path is the amount of all the numbers in it's cells.

For example, let's say I have this matrix: 

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

so {1,2,4} is a path, and {1,3,4} is another path.

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

I need to solve it recursively. The pseudo code should be 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 recursives 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 retrieve something, what?

I know it's not current but that's the general idea, can someone help me solve this? Thanks!

Upvotes: 5

Views: 315

Answers (2)

Stefan Haustein
Stefan Haustein

Reputation: 18813

You should be able to use Dijstra's algorithm, where the nodes are "between" the cells of the matrix and the connections are implied by the weights of the cells.

For a detailed answer, please refer to this question: Javascript: Pathfinding in a (50000*50000 grid) 2d array?

Upvotes: 0

Nikolas
Nikolas

Reputation: 44496

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

  1. You have to test the random way first and get its sum.
  2. Approach systematically. Try another one and if its sum is larger in the progress, stop it and try the another one.
  3. If you find the smallest sum way, capture its sum (and directions) and try another one until there is no way left
  4. You have the result :)

This solution would work for direct paths. I mean you always step to the right or down direction. Not going back (up or left) - if you start from top-left cell and end in the bottom-right one.

Check the difference:

enter image description here

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

Generally said, to find the best solution is in this case very complicated and you have to specify if you set any limits or not.

Upvotes: 1

Related Questions