0
$\begingroup$

I am trying to solve this problem, and i have tried multiple methods, but i must be missing something, here is the problem: Given a matrix MxN. Find the shortest path from (1,1) to (M,N), where each number in the matrix represents the costs and one can only move horizontal and vertical:

e.g.

M = 

1, 50,50,50,50;
1, 50,1, 1, 1 ;
1, 1, 1, 50,1 ;
50,50,50,50,1 ;
50,50,50,50,1 ;

where the shortest path is: (1,1) , (2,1) , (3,1) , (3,2) , (3,3) , (2,3) , (2,4) , (2,5) , (3,5) , (4,5) , (5,5)

Initially i tried to solve this recursion using Dynamic Programming:

SP(i,j) = {
    M[i][j], if i=M and j=N
    min(SP(i+1,j), SP(i-1,j), SP(i,j+1), SP(i,j-1)) + M[i][j], otherwise
}

It however loops infinitely since it calls in every direction e.g. going right is dependent on going left and so on..

Can anyone help me solve this problem?

Improve this question
$\endgroup$
1
  • $\begingroup$ when you said "only move horizontal and vertical", it seems that you can go from A to B and may be return to A, so you can generate loops. Therefore, you cannot handle the problem with dynamic programming, at least that you just move right and down directions. If you have loops you should attack with a SSPP. $\endgroup$
    – Jonathan Prieto-Cubides
    Commented Mar 25, 2015 at 5:03

1 Answer 1

Reset to default
2
$\begingroup$

Treat the matrix as a weighted graph and use your favourite least-weight path algorithm.

To transform the matrix into a graph, say that the cost of going along the edge from $a$ to $b$ is the cost of visiting $b$. You'll need to separately add the cost of visiting the first node to the cost of any path the algorithm comes up with.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.