Finding path in Minimum Cost Path algo using Dynamic Programming

Question

• Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0).

• Each cell of the matrix represents a cost to traverse through that cell. Total cost of a path to reach (m, n) is sum of all the costs on that path (including both source and destination).

• You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed.

• You may assume that all costs are positive integers.

I was able to find the minimum cost and this article turned out to be very helpful:

http://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/

_{(source: cloudfront.net)}

But it does not tell the actual path that must be followed which in the above example is (0, 0) –> (0, 1) –> (1, 2) –> (2, 2). How can I find the path?

Answer 1

As we keep the track using arrows in logest common subsequence problem using an auxillary array, similarly here we can keep track of which element returned the minimum value. Then starting from cell (m,n) backtrack as per the arrows you have stored.

Answer 2

When you're searching for the path, also keep track of the decisions that you're making, i.e. when you're selecting the minimum in this statement (taken from the article you're referencing):

return cost[m][n] + min( minCost(cost, m-1, n-1),
                           minCost(cost, m-1, n),
                           minCost(cost, m, n-1) );

You also need to keep track of which element was the minimum (e.g. in a separate matrix with directions (left, up, up-left)). Then you can backtrack from the final element of the matrix and reconstruct the path.

This is basically Levenshtein distance with back-tracking, you can find a pseudo-code implementation e.g. here