Problem Detail: 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?
Asked By : Wojciech Kulik
Answered By : Wojciech Kulik
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]);
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/25968
