Vini
Vini

Reputation: 323

Finding path in Minimum Cost Path algo using Dynamic Programming

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/

dp
(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?

Upvotes: 1

Views: 7224

Answers (2)

user3552407
user3552407

Reputation: 381

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.

Upvotes: 0

ales_t
ales_t

Reputation: 2017

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

Upvotes: 2

Related Questions