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?