2
$\begingroup$

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}

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.