# Shortest path in a matrix

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?

• 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. – jonaprieto Mar 25 '15 at 5:03

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.