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

c(v) &lt;= c(u) and g &lt; d[u][v]


but it should be

(c(v) &lt;= c(u) or v = t) and g &lt; 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) &lt;= c(u)


on line 3 to

if c(v) &lt;= 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.