I'm looking for an algorithm that do the following thing.

Given $n$ the number of rows and columns of a matrix of positive integers.

Given $(x_1,y_1)$ the starting coordinates.

Given $(x_2,y_2)$ the ending coordinates.

and $k$ an integer.

This are some rules of how you can travel through the matrix:

  • When stepped in some coordinate $(x,y)$ with a given value $w$, you can travel to $(x \pm w,y)$ or any value between this range or $(x ,y \pm w)$ or any value between this range.

  • Also you can spend the integer $k$ in order to travel a little further in a row or a column. For example with $k=4$ you can travel to $(x ,y + w + 3)$ spending $3$ of your $k$. In this case, now you only have $k=1$ to spend.

The objective here is find the minimum path between $(x_1,y_1)$ and $(x_2,y_2)$.

I already implemented an algorithm that do this in $O(n^3k)$, the problem it's that given the implementation it's very difficult to justify its correctness.

How would you resolve this problem in a way that is easily shown it's correctness?


A conceptually simple approach is to form an unweighted graph with $(k+1)n^2$ vertices: one copy of the matrix for each possible number of credits remaining. Each edge represents a way you can travel in a single step. You start at $(x_1,y_1,k)$ and want to end at $(x_1,y_1,0)$. Now, look for the shortest path in this graph. There is a straightforward algorithm to find the shortest unweighted path in such a graph. Also, any good algorithms textbook will tell you how to justify its correctness.

This should produce an approach where it is very easy to justify its correctness. Its running time is not the best possible, but it's not too terrible, either. The running time is something like $O(n^2 k^2 w)$: the degree of each vertex is $O(kw)$, and there are $O(n^2 k)$ vertices, so $O(n^2 k^2 w)$ edges in total. This is $O(n^3 k^2)$, so not too much slower than your algorithm. If your primary criterion is ease of justifying correctness, this might be a simple solution.

| cite | improve this answer | |
  • $\begingroup$ @FranckN, see my revised answer for more details. $\endgroup$ – D.W. Jun 4 '14 at 23:29

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.