I am trying to solve this problem, and i have tried multiple methods, but i must
ID: 647078 • Letter: I
Question
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 =
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:
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?
Explanation / Answer
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.