I am trying to solve this problem, and i have tried multiple methods, but i must

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.