CODEWITHSUNDEEP
algorithmdynamic-programming
Abdul Hanan
Abdul Hanan

Reputation: 1

Dynamic Programming to find minimal route

I am getting problems in devising solution for this DP problem

Suppose you want to travel from city A to city B. There are n stopovers on the way where you have a number of choices to select a hotel to stay at every stopover. The cost involved is the travel cost to some hotel at a stopover (let’s call it tij where i is the current stopover and j is the next one) and the cost of staying at a hotel at stopover j (let’s call this sj). Devise a dynamic programming algorithm to select an optimal route and a hotel in city B that minimizes the cost of the whole trip. Analyze its correctness and running time.

Upvotes: 0

Views: 1099

Answers (1)

Liu Wu
Liu Wu

Reputation: 41

Here's a possibly correct algorithm: Define the stop as a1,a2,a3,a4,a5,a6.....an and the smallest cost at each stop be c1,c2,c3,c4,c5...cn

for the first stop. Calculate the cost of route from city A to a1 and store it in c1.

for the second stop. Calculate the cost of route from A to a2, and calculate the cost of route from a1 to a2 plus c1. Choose the smaller cost and store it to c2

for the third stop. Calculate the cost of route from A to a3, the cost of a1 to a3 plus c1, and the cost of a2 to a3 plus c2. Choose the smallest cost and store it to c3

.... ... .

Then at last, we can find cn+1, the smallest cost of route from A to B with the same steps above

The dynamic expression be ci=min(c1+t(1,i),c2+t(2,i),c3+t(3,i),....,c(i-1)+t(i-1,i))

We trying all the possible routes to each stop and find the smallest cost and thus why the answer is route we choose is minimized

The running time of such algorithm is O(n^2), thinking about build a two dimensional array with size n*n

Upvotes: 2

Related Questions