CODEWITHSUNDEEP
javaarraysalgorithmshortest-path
rakesh r
rakesh r

Reputation: 475

How to find Path of Lowest Cost in 2D matrix

i have a Challenge the objective is to get the lowest cost of the path. The path can proceed horizontally or diagonally. not vertically. like below. and the first and last row are also adjacent.

enter image description here

for example see below matrix:

enter image description here

output for 1st matrix :
16
1 2 3 4 4 5-->path row number

output for second matrix:
11
1 2 1 5 4 5-->path row number

am doing it in java, am getting the Lowest path but am not getting the path to print the path using row numbers.

int minCost(int cost[r][r], int m, int n)
{
   if (n < 0 || m < 0)
      return Integer.MAX_VALUE;;
   else if ((m == r-1 && n == c-1)|| n+1>=c)
      return cost[m][n];
   else
      return cost[m][n] + min( minCost(cost, m+1>=r?r-1:m+1,n+1),
                                         minCost(cost, m,n+1),
                                minCost(cost, m-1>=0?m-1:r-1,n+1));
    }
// calling it 
minCost(cost, 0, 0);

How to get the row numbers for shortest path?

Upvotes: 0

Views: 1971

Answers (2)

Cheng Chen
Cheng Chen

Reputation: 43531

Your algorithm is quite inefficient. The best solution I can think is calculating it backwards(from right to left). Consider the right 2 columns of your second matrix:

8 6
7 4
9 5
2 6 
2 3

If now we are on the cell with value 8, the next step can be 6/4/3. Of course we choose 3 because we want a smaller cost. If now we are on the cell with value 7, the next step can be 6/4/5, we will choose 4. So the two columns can merged into one column:

11   //8+3
11   //7+4
13   //9+4
5    //2+3
5    //2+3

Now repeat the last two columns:

2  11
2  11
9  13
3  5
1  5

Finally the matrix will be merged into one column, the smallest value in the column has the lowest cost.

Upvotes: 2

user5639737
user5639737

Reputation:

I'll try to expand on fabian's comment:

It's clear that your minCost function will return the same values if called with the same arguments. In your algorithm, it indeed does get called lots of times with the same values. Every call for column zero will generate 3 calls for column 1, which in turn generate 9 calls for column 2, etc. The last column will get a huge number of calls (3^r as fabian pointed), most of them recalculating the very same values for other calls.

The idea is to store these values so they don't need to be recalculated every time they are needed. A very simple way of doing this is to create a new matrix of the same size as the original and calculating, column by column, the minimum sum for getting to each cell. The first column will be trivial (just copy from the original array, as there is only one step involved), and then proceed for the other columns reusing the values already calculated.

After that, you can optimize space usage by replacing the second matrix by only two columns, as you are not going to need column n-1 once you have column n fully calculated. This can be a bit tricky, so if you're unsure I recommend using the full array the first time.

Upvotes: 0

Related Questions