# Cheapest path in a matrix

Consider an $m \times n$ matrix and I want to find the cheapest path from $a_{1,1}$ to $a_{m,n}$, given one can only move right or down.

Is there any algorithm to calculate this? What would be the most efficient way to do this?

Edit: Matrix entries are considered to be the cost of one step.

For eg: the following matrix has the cheapest cost of $(10+2+2+2+3) = 19$

\begin{bmatrix} 10 & 5 & 6 \\ 2 & 4 & 7 \\ 2 & 2 & 3 \end{bmatrix}

• Are the matrix entries considered as costs to go one step? Or do the entries represent costs in some way? – coffeemath Feb 19 '18 at 11:52
• This depends on what you consider to be cheap. – user Feb 19 '18 at 11:52
• Matrix entries are considered as costs of one step. – MessitÖzil Feb 19 '18 at 11:53
• You shall write it in your question. – user Feb 19 '18 at 11:53
• It's problem 81 from the Project Euler (projecteuler.net) – HEKTO Feb 19 '18 at 20:15

One method is Dijkstra's_algorithm under: https://en.wikipedia.org/wiki/Dynamic_programming

I think you can use smallest cost instead of shortest path in your example.

Dijkstra's algorithm for the shortest path problem

From a dynamic programming point of view, Dijkstra's algorithm for the shortest path problem is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.[6][7][8]

In fact, Dijkstra's explanation of the logic behind the algorithm,[9] namely

Problem 2. Find the path of minimum total length between two given nodes P and Q.

We use the fact that, if R is a node on the minimal path from P to Q, knowledge of the latter implies the knowledge of the minimal path from P to R.

is a paraphrasing of Bellman's famous Principle of Optimality in the context of the shortest path problem.