A car sets off from S and drives to D as shown in the figure. Gas sta tions have been set at some intersections (asterisks). The car can only run along sides and a full tank runs K sides. The driver has to pay the following fees:

● To re fill a full tank of gas, pay $A.

● If the car goes back (either x coordinate or y coordinate decreases when driving one more side), pay $B.

● The driver can set up some ex tra gas sta tions, but has to pay $C for each setup. Neither S or D allows a gas sta tion setup.

We assume that the car sets off with a full tank of gas for free. Design an algorithm to re turn a path from S to D that spends minimal money. (pseudo code required) 

Transcribed Image Text:

S(1, 1) 2 3 2 3 n y : n X D(n,n) S(1, 1) 2 3 2 3 n y : n X D(n,n)

Answer rating: 100% (QA)

heres a pseudocode algorithm to find the path from S to D that minimizes the cost pseudo function mi... View the full answer