Shortest Path Algorithm with Fuel Limit and Variable Fueling

Question

Suppose you have an undirected weighted graph. You want to find the shortest path from the source to the target node, starting with the initial “fuel”. The weight of each edge is equal to the amount of "fuel" that you lose going through the edge. On each node, you can have a predetermined amount of fuel added to your amount of fuel - this value can be 0. A node can be visited more than once, but fuel will be added only when the node is first taken. ** All nodes may have varying amounts of fuel to provide.

This problem may be related to the train leaving from city A to city B. Even if the two are directly connected by a simple track, there is a shortage of coal, so the train does not have enough fuel to make the trip. Instead, it should make a much shorter trip from the city And to city C, which, as you know, has enough fuel to cover the trip back to A, and then forward to B. Thus, the shortest route will be the distance from A to C plus the distance from C to A plus the distance from A to B. We assume that fuel cost and distance are equivalent.

I saw an example where nodes always fill the "tank" to maximum capacity, but I have not seen an algorithm that processes different amounts of refueling on different nodes. What is an effective algorithm to solve this problem?

Answer 1

Unfortunately, this problem is NP-hard. Given an instance of the salesman route from s to t with a decision threshold d (is there an st path for all vertices of length no more than d?), Make an instance of this problem as follows. Add a new destination vertex associated with the t very long edge. Give starting fuel d. Set the length of the new edge and the fuel at each vertex except the destination, so that (1) the total amount of fuel at all the vertices is equal to the length of the new edge (2), it is impossible to use a new edge without collecting all the fuel. You can only reach your destination when there is a short seller route.

Accordingly, the algorithms for this problem will resemble the algorithms for TSP. The pre-process, building a complete graph on the source, target and peaks with non-zero fuel. The length of each edge is equal to the distance.

If there are few enough special vertices, then exponential time (O (2 ^ n poly (n))) dynamic programming is possible. For each pair consisting of a subset of vertices (in decreasing order of size) and a vertex in that subset, determine the cheapest way to visit the entire subset and terminate at that vertex. Do this efficiently using pre-calculated results for the subset minus the vertex and every possible last waypoint. There is an optimization that reduces solutions that are worse than a known solution, which can help if there is no need to use a lot of waypoints.

Otherwise, reproduction can be whole programming. Here is one wording, most likely improved. Let x(i, e) be a variable equal to 1 if the directional edge e taken as the i th step (counting from zero) else 0. Let f(v) be the fuel available at the vertex v . Let y(i) be the variable that is the fuel in the hand after steps i . Suppose the total number of steps is T

 minimize sum_i sum_{edges e} cost(e) x(i, e) subject to for each i, for each vertex v, sum_{edges e with head v} x(i, e) - sum_{edges e with tail v} x(i + 1, e) = -1 if i = 0 and v is the source 1 if i + 1 = T and v is the target 0 otherwise for each vertex v, sum_i sum_{edges e with head v} x(i, e) <= 1 for each vertex v, sum_i sum_{edges e with tail v} x(i, e) <= 1 y(0) <= initial fuel for each i, y(i) >= sum_{edges e} cost(e) x(i, e) for each i, for each vertex v, y(i + 1) <= y(i) + sum_{edges e} (-cost(e) + f(head of e)) x(i, e) for each i, y(i) >= 0 for each edge e, x(e) in {0, 1} 

Answer 2

There is no efficient algorithm for this problem. If you take an existing graph G size n , you can give each edge a weight of 1, each node a deposit of 5, and then add a new node that you are trying to move to connect to each node with a weight of 4 * (n -1) . Now the existence of a path from the source to the target node in this graph is equivalent to the existence of a Hamiltonian path in G , which is a well-known np-complete problem. (For more details see http://en.wikipedia.org/wiki/Hamiltonian_path .)

However, you can do better than a naive recursive solution for most graphs. First do the first width search from the target node so that the distance to the node from the target is known. Now you can take the basic idea of ​​finding Dijkstra A *. Search for all paths from the source, using the priority queue to always try to grow the path, the current distance + minimum to the target, at least. And to reduce performance, you probably also want to reset all the paths that went back to the node they had previously visited, with the exception of a lower amount of fuel. (This will avoid stupid paths that move back and forth around the hinges as the fuel runs out.)

Answer 3

Assuming fuel consumption as a positive weight and the ability to add fuel as a negative weight and further process the original fuel available as another negative weighted margin, you can use Bellman Ford to solve this problem as the shortest path to a single source.

According to this answer , elsewhere, undirected graphs can be resolved by replacing each edge with two in both directions. The only limitation that I'm not sure about is the part where you can only refuel once. This algorithm can be naturally considered, but I'm not sure.