The Gas Station Problem - fast implementation
Your recurrence relationship isn't quite right -- you need to relate the input parameter f to f1 and f2 somehow.  I think you can get rid of f2 completely:

checkTank(f) = if f &lt;= U then f else INF
D[v][f] = min(u, f1 | u-&gt;v in Edges and f1 in 0..tankCapacity)
             { D[u][f1] + checkTank(f - f1 + distance(u, v)) * fuelRate[u] }


Entries D[v][f] for values of f which would imply putting more gas in the tank than it can hold will correctly get assigned INF by the above.  (Here I assume that adding any nonnegative value to or multiplying any positive value with INF yields INF again; in an actual implementation you might want to specially check and avoid further processing of such values.)

But in any case, the algorithm in the paper is fast because they exploit a dominance rule (Lemma 2.1) that implies that an optimal solution can always be found even if you only look at O(n) particular different gas tank levels at each node, and you aren't making use of that here.  If you don't make use of that same property, I think your algorithm will be at best pseudopolynomial (they say this in the paper; BTW that doesn't necessarily make it a terrible algorithm in practice) and in effect usable only with integer-weight fuel amounts.

Regarding adding the missing edges: For the case where you don't limit the number of stops, the running time is O(n^3), so it's safe to run Floyd-Warshall at the beginning to calculate the minimum path distance between all pairs of vertices that lack an edge, as it's also only O(n^3) and therefore doesn't increase the running time asymptotically.

At first glance it seems possible to accept an incomplete graph, and allow "fill stops" at which 0 fuel is filled.  But this invalidates Lemma 2.1, since now there can be graphs in which an optimal path involves filling up less than the full amount at some node w, before travelling to some node u with higher cost, "filling up" with 0 fuel there, and then travelling on to reach (on an empty tank) some other node v with cheaper fuel than w.  You can play around with Lemma 2.1 to allow arbitrarily long strings of special "0-fill" stops between "real" stops, and this works, but it doesn't buy you anything: for each vertex u, instead of having to consider all possible neighbours w of u and their distances d(w, u) to u, you'll have to consider all possible vertices w and the lengths of their shortest paths to u, which means that you might as well calculate them all at the start and make edges with their weights.

Finally you can discard/ignore/avoid calculating any edges longer than U or which violate the Triangle Inequality (in fact these constraints also apply to any edges already in the original graph).