# Kth Optimal path in a matrix

I had the following question I was trying to solve:

You are given a `n*n` matrix. Every cell of the matrix contain some value (positive).

You are currently at (0,0) and you have to go to right most and bottom most cell `((n-1)*(n-1))`. You can move either right or down.

I am aware of finding the most optimal solution for this using the dynamic programming approach. But what is the best way to find the `k`th optimal solution?

• This is related to Project Euler problem #81. – user40980 Oct 26 '14 at 20:31
• It's not entirely clear from your description what you mean by "optimal solution". What are you optimizing for? – Periata Breatta Oct 27 '14 at 0:05
• Optimal meaning minimum path from (0, 0) to (n, n). – redDragon Oct 27 '14 at 14:13

In the classic version(k = 1, solve for best path), the key insight used is as follows.

1) In computing best path for cell (i, j) (best[i][j] is the cost of best path from top-left to (i, j)), we notice that this path could either come from it's left or upper neighbor. Thus we do (leaving aside corner cases for a moment)

``````best[i][j] = min(best[i][j-1], best[i-1][j]) + value[i][j]
``````

2) Now, if we want to compute k best paths from top-left corner to (i, j), we can again follow a similar, but more general technique. Here, best[i][j] can be thought of as a list of k best paths instead of one best path.

``````best[i][j] = merge_and_select_k(best[i-1][j], best[i][j-1], k)
``````

merge_and_select_k takes two input lists, an integer k - It concatenates the two lists and keeps only the k best values. Of course, you must also add value[i][j] to all these selected items.

3) Loop over the matrix, just like in the classic version and compute best[i][j] for every i and j. Your final result is best[n][n][k].

4) This works because, we only need to consider best[i-1][j] and best[i][j-1] for computing best[i][j]. Time complexity is O(k * n * n) and space complexity is O(k * n), as we only need keep the values for current and previous rows.

• Space complexity is `O(k*n)` only if we're not interested in the path itself - but only in it's length. Otherwise - how is this different to the addendum to my own answer? – Ordous Dec 5 '14 at 16:29
• Aah, didn't see your addendum. Space complexity is still O(k * n) if we are only interested in the path values. It's O(k * n * n) if we are also interested in the actual paths(routes) themselves. – VinyleEm Dec 5 '14 at 16:33
• Can you explain merge_and_select_k a bit more? – redDragon Dec 6 '14 at 2:32
• I think an example would suffice. merge_and_select_k([3, 4, 12], [1, 21, 100], 3) should give 3 best values from the two lists -> [12, 21, 100]. – VinyleEm Dec 6 '14 at 7:30
• Thanks for the idea. If we need to store even the path and not just the distance, what would you suggest? – redDragon Dec 8 '14 at 0:02

This is likely not the best way, but given there are no other answers, here is a way.

The problem of finding the k-th optimal path is AFAIK not very well studied for matrices, but is quite common in graphs. In fact, Wikipedia has some examples of how it can be done in a weighted directed graph. Hence a solution that transforms you matrix to a graph and employs the algorithm from the Wiki:

Algorithm:

Transform your matrix into a weighted directed graph. Every entry in your matrix will be a vertex, and vertex A has an edge to vertex B iff A was above or to the left of B in the matrix. The weight of the edge is the end vertex value.

Now, use Yen's algorithm to find the k-th optimal path. (it's a fairly known, but long algorithm, so not posting it here).

Complexity

Creating the graph is trivial and takes linear time in the size of your matrix. The resulting graph has `N^2` vertexes and `2N(N-1)` edges. Yen's algorithm requires K*l calls to Dijkstra, where l is the length of the spur paths (In this case it's `2N`, since all paths here are at most `2N` length).

Hence the total runtime is expected to be `O(K * N^3 * log(N))`. This is a very pessimistic bound, but you may find that the cubic behaviour is indeed true - this solution does not use any pros from the graph structure being matrix-like.

This solution will be faster than the above, clocking at `O(K * N^2)`. However, it uses `O(K * N^2)` space, which is much larger than `O(N * (K + N))` of the above solution. I guess here you would need to make a decision on what resource is more scarce.