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:
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).
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
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.
After thinking about this a bit more:
There is an obvious naive solution that just takes the standard dynamic programming approach, and instead of storing the shortest path to each node stores the k shortest paths.
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.