Question

There are n trading posts along a river. At any of the posts you can rent a canoe to be returned at any other post downstream. (It is next to impossible to paddle against the current.) For each possible departure point i and each possible arrival point j the cost of a rental from i to j is known. However, it can happen that the cost of renting from i to j is higher than the total cost of a series of shorter rentals. In this case you can return the first canoe at some post k between i and j and continue your journey in a second canoe. There is no extra charge for changing canoes in this way. Give an efficient algorithm to determine the minimum cost of a trip by canoe from each possible departure point i to each possible arrival point j. In terms of n, how much time is needed by your algorithm?

Answer 1

Answer :

Consider the following data :

• x is the departure point.
• y is the arrival point.
• A[x,y] is the cost of renting a canoe to travel from post x to post y.
• There may be many routes to travel from post x to post y. But we need to assume the cheapest cost for the trip.
• Let T[1, z] be the cheapest cost of travelling from post 1 to post z where z=1,2,3...n.

The algorithm to find the T[1, z], where k=2 to n is as shown below :

Algorithm:

T[1,1]= 0 //the cost of travelling from post 1 to post 1 is 0.

//to find the cost of travelling from post 1 to post z

for z = 2 to n do

T[1,z]= min_y-1..z-1{T[1,y] + A[y,z]}

The running time of the algorithm is O(n²).

Similarly, we can find the T [2,z] where z=3 to n, T [3,z] where z=4 to n and so on.

We can find the minimum cost by adding the cheapest costs between the posts along the path from post x to post y.

Thus, the running time is O(n³).