Understanding an algorithm for the gas station problem

Problem Detail: 

In the gas station problem we are given $n$ cities $\{ 0, \ldots, n-1 \}$ and roads between them. Each road has length and each city defines price of the fuel. One unit of road costs one unit of fuel. Our goal is to go from a source to a destination in the cheapest possible way. Our tank is limited by some value.

I try to understand the algorithm, so I manually wrote down steps to calculate the solution. Unfortunately I got stuck - at some point there are no edges to consider, I don't know why, maybe I'm missing something.

Example:
road:
0 ----------- 1 ------------ 2 -------------- 3
(it doesn't have to be that simple, it could be any graph i.e. there could be roads between 0->2, 0->3, 1->3 etc.)

Source: 0, Destination: 3, Tank: 10 units
Fuel prices: 0: 10 units, 1: 10 units, 2: 20 units, 3: 12 units
Lengths: 0->1: 9 units, 1->2: 1 unit, 2->3: 7 units
Optimal solution: fill 9 units at 0 and 8 units at 1. Total cost then is 170 units (9 * 10 + 8 * 10).

So I tried to calculate it as shown here (paragraph 2.2)

GV[u] is defined as: GV[u] = { TankCapacity - length[w][u] | w in Cities and fuelPrice[w] < fuelPrice[v] and length[w][u] <= TankCapacity } U {0}  so in my case: GV[0] = {0} GV[1] = {0} GV[2] = {0, 3, 9} GV[3] = {0}  D(u,g) - minimum cost to get from u to t starting with g units of fuel in tank: D(t,0) = 0, otherwise: D(u,g) = min (foreach length[u][v] <= TankCapacity)          {             D(v,0) + (length[u][v] - g) * fuelPrice[u]                             : if  fuelPrice[v] <= fuelPrice[u] and g <= length[u][v]            D(v, TankCapacity - length[u][v]) + (TankCapacity - g) * fuelPrice[u]  : if  fuelPrice[v] > fuelPrice[u]          }  so in my case: D(0,0) = min { D(1,0) + 9*10 }  - D(0,0) should contain minimum cost from 0->3 D(1,0) = min { D(2,9) + 10*10 } - in OPT we should tank here only 8 units :( D(2,9) = min { ??? - no edges which follows the condition from the reccurence   Nevertheless D(0,0) = 90 + 100 + smth, so it's already too much.  To achieve the optimal solution algorithm should calculate D(2,7) because the optimal route is:    (0,0) -> (1,0) -> (2, 7) -> (3, 0) [(v, g): v - city, g - fuel in tank].  If we look at G[2] there is no "7", so algorithm doesn't even assume to calculate D(2,7),  so how can it return optimal solutions? 

Recurrence from the document doesn't seem to work or what's more likely I do something wrong.

Could anybody help me with this?

Asked By : Wojciech Kulik

Answered By : j_random_hacker

The problem is in the condition for the first argument to min() in Equation (4) on p. 7. It's currently

c(v) <= c(u) and g < d[u][v] 

but it should be

(c(v) <= c(u) or v = t) and g < d[u][v] 

to force arrival at t to have no gas left. (Just as with my explanation below for the bug in Fill-Row(u, q), we are never interested in the cost of gas at t. And as with there, another way to fix the problem would be to overwrite c(t) with 0 at the start of the algorithm.)

Fixing this mistake (in the published algorithm), combined with adding in the missing edges as I describe below (your mistake :-P), should be enough to get everything working.

---

One thing you're missing is that the graph G must be complete (first sentence of section 2, p. 4) -- and if it's not complete, any missing edges must be added, with the weights found by taking minimum path lengths in the graph. So e.g. in your example graph, there should be (among others) an edge from 1 to 3 with weight 8 (corresponding to the path via 2), so that in fact GV[3] = { 0, 2 }.

I'm not sure whether that will completely solve the problem for you, but it should help.

Separately, I think there's a bug in the Fill-Row(u, q) algorithm on p. 6: this algorithm should treat the case q=1 specially, but it doesn't. I believe it could be fixed by changing

if c(v) <= c(u) 

on line 3 to

if c(v) <= c(u) or q = 1 

to force any final leg to arrive at the destination empty. (Intuitively, we should always disregard the price of gas at the final destination, t.) Another way around this would be to overwrite c(t) with 0 at the outset.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25906