2
$\begingroup$

Recently I was asking about the algorithm to solve The Gas Station Problem and I got useful answer. Unfortunately solution with transforming a graph to complete graph and then preparing another one to find the shortest path (as described in paragraph 4) is really slow in case of my constraints.

I figured out how to implement much faster version. It's way better, but has a bottleneck :-(. Let me first describe my implementation. It's really simple:

I use BFS and relaxation method to calculate D[destination][0]:

D[v][f] - minimum cost to get from u to v with remaining f units of fuel at this city.

minFuel - minimum remaining fuel at v = max(0, f1 - distance(u,v))
maxFuel - maximum remaining fuel at v = tankCapacity - distance(u,v)

D[source][0] = 0
D[v][f] = min((u,v), f1, f2 | u->v in Edges and f1 in 0..tankCapacity and f2 in minFuel..maxFuel)
             { D[u][f1] + (f2 - f1 + distance(u,v)) * fuelRate[u] }

The bottleneck is because of going through all possible values (f1, f2).

Pseudocode:

queue.push(source);
D[source][0] = 0
visited[source] = true

while(!queue.empty)
    current = queue.pop

    foreach (current,v) in Edges
       if !visited[v]
           queue.push(v)
           visited[v] = true

        for f1 in 0..tankCapacity
           if D[current][f1] == infinity
              continue

            minFuel = max(0, f1 - distance[current,v])
            maxFuel = tankCapacity - distance[current,v]

            for f2 in minFuel..maxFuel
                toRefill = f2 - f1 + distance[current,v]
                newCost =  D[current][f1] + toRefill * fuelRate[current]
                if (newCost < D[v][f2])
                   D[v][f2] = newCost


return D[destination][0]

Constraints (only integers):

maximum vertices:      1000
maximum edges:         10000
maximum distance:      100
maximum fuel rate:     100
maximum tank capacity: 100

Does anybody have an idea how to improve this algorithm to make it faster?

$\endgroup$
  • 1
    $\begingroup$ If you're asking for improvements to the algorithm, please express it in pseudocode: people aren't going to wade through 200 lines of C. If you're asking for improvements to the implementation, your question is off-topic here. $\endgroup$ – David Richerby May 21 '14 at 16:26
3
$\begingroup$

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 <= U then f else INF
D[v][f] = min(u, f1 | u->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).

$\endgroup$
  • $\begingroup$ My algorithm is still better (if I'm right), because it'll visit each edge and each vertex once, then for each edge maximum 100*100 iterations through pairs (f1,f2), so complexity will be O(|E| * tankCapacity^2), so for maximum edges and tank capacity we will have O(|E|^2). $\endgroup$ – Wojciech Kulik May 25 '14 at 12:43
  • $\begingroup$ In the algorithm you described the constant hidden in O is crucial. For example for 1000 vertices only Floyd-Warshall will take 1000^3 iterations. Going the way described in the document (create a new graph with vertices (u,g) and find the shortest path) we need to create a new graph with much more vertices and then use Dijkstra's algorithm to find the shortest path, so complexity will be much worse. My algorithm won't do more than 10000^2 iterations (assuming constraints). In fact it will be much less, because loop through f2 is highly limited. $\endgroup$ – Wojciech Kulik May 25 '14 at 13:00
  • $\begingroup$ I missed the constraint on the maximum fuel rate in your question, which isn't mentioned in the paper. Nevertheless the problem described in the paper has fuel costs in the positive real numbers, so the fact that there's an upper bound of 100 doesn't affect the complexity -- fractional fuel costs are allowed. If you are in fact restricting to only integer fuel costs, then yes, there are then only 101 distinct possible costs, and your pseudopolynomial time algorithm will probably be faster for the set of parameter limits you have chosen. $\endgroup$ – j_random_hacker May 25 '14 at 20:50
  • $\begingroup$ Secondly I'm not sure what you mean when you talk about "adding vertices" -- my suggestion is to use F-W to add edges between existing vertices. $\endgroup$ – j_random_hacker May 25 '14 at 20:51
  • $\begingroup$ Yes, my algorithm should only consider integers. About adding vertices - in the document (right after equation 4) it is suggested to prepare a new graph with vertices with two parameters (v,g) and then to find the shortest path. Anyway thank you for the time that you spent to prepare this answer and to help me :-). $\endgroup$ – Wojciech Kulik May 25 '14 at 22:57
0
$\begingroup$

Finally I had prepared a solution with good enough complexity. Friend from my college had given me some hints and I managed to implement it. Maybe it will help someone, so I decided to describe this solution here.

The idea is very simple, we use Dijkstra's Algorithm, but instead simple vertices we have pairs (v, f). v - vertex id, f - fuel in tank. This solution is much faster, because we don't need to go through all values of "f" and also when we process a vertex, it already has an optimal solution. So when we'll get to the destination vertex, we can stop further processing.

Dijkstra's Algorithm needs to get a minimum value in each iteration, so it's good to use heap structure for a priority queue.

Pseudocode:

D[v][f]        - minimum cost to get from source to v with f units of fuel
distance[u][v] - distance between u and v


relax(tankCapacity, u, f, newCost):
    if (f >= 0 and f <= tankCapacity and D[u][f] > newCost)
        D[u][f] = newCost
        heap_push_or_update(D[u][f])


solve(tankCapacity, source, destination):
    foreach (v, f)
        D[v][f] = infinity

    D[source][0] = 0
    heap_push(D[source][0])

    while not heap_empty()
        (v, f) = heap_pop_min();

        //don't go further than destination
        if (v == destination and f == 0)
            return D[v][0];

        //stay in the city and refill more fuel - it can improve D[v][f + 1]
        newCost = D[v][f] + fuelRate[v];
        relax(tankCapacity, v, f + 1, newCost);

        //go to the adjacent cities "u" without refilling - it can improve D[u][f - d]  
        foreach (v, u) in Edges
            relax(tankCapacity, u, f - distance[v][u], D[v][f]);
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.