[Solved]: Shortest path in a matrix

Problem Detail: 

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?

Asked By : saph

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40690