How to find the shortest route in a graph with additional route requirements?

Question

Algorithms

I have a graph, each edge has some positive weight. To find the shortest route between two points, I use Dijkstra's algorithm. I have an additional condition: a gas station system. Those. in some of the vertices there are "gas stations" that replenish our travel reserve, and without gas stations, I can only move by some n (n is the sum of the weights of the edges passed from the gas station). In this case, how should I minimize the number of gas stations on the route? If we are in a node with fueling, we don't necessarily have to use it.

Answer 1

First, we look for all possible paths with gas stations: ([current gas station: how far does it fill up] + [current fuel supply: what is the maximum distance you can drive without refueling] - [the sum of the edges of the path from the current node to the next gas station or destination] ) > 0.
We select all possible options so that there is always fuel in the tank.
Then, only from them, we are looking for the minimum number of gas stations on the shortest path.

Answer 2

With these constraints, it is possible to create an artificial graph, where each vertex corresponds to a vertex in the original graph and some fuel supply (I will denote such a vertex as (v, f) - at the vertex v with fuel f).
There will be up to 500*10000 vertices in such a graph. For each edge v->u of length l in the original graph, we create an edge from vertex (v, f) to vertex (u, fl) for all f (i.e. from vertex v, having f fuel, you can get to vertex u, having fl of fuel). These edges cost 0. Also, at each vertex v where there is fuel, add an edge (v, f) -> (v, n) with price 1 (fueled to the limit). There will be up to 500*10000 + 500*10000 edges in the graph.
Now run a 2-queue breadth-first walk there, or a deque from vertex (start, n) until you find a path to any vertex (finish, f). The length of the path will be equal to the number of gas stations. Transitions along the edges at cost 1 are the filling process, along the edges at cost 0 they are simply movements in the original graph.
This is a well-known generalization of breadth-first search on a 0-1 graph:
When you take a vertex from a deque and look at all its neighbors, if the length of the edge to the neighbor is 1, then put the end of the edge at the end of the deque, and if the price is 0, then put it at the beginning. With two queues, this is done: while the queues are not empty, we take a vertex from the current queue and put its neighbors at a distance of 0 to the end of the same queue, and neighbors through an edge of length 1 - to the second queue. When the current queue is empty, we move on to another one, and so on.

Answer 3

OPTION 1. Distance is a priority over the number of gas stations.
My solution is to store at each vertex not just a number of the distance traveled, but a list: “distance / fuel supply / previous vertex”. Both distance and fuel do not decrease.
With these lists, you can do the following operations:
1. Add distance + use fuel. For each element of the list, distance′ = distance + x, fuel′ = fuel − y. If there is a shortage of fuel - well, no luck, this element will not be in the list.
2. Add distance + use up fuel + refuel. Similarly, but we leave one element - corresponding to the smallest distance where there is enough fuel. distance′ = distance + x, fuel′ = full tank.
3. Add another element to the list. Then we remove from the list those elements where the distance is not less, and the fuel supply is not more.
After that, we optimize the filling stations on the optimal route.
If the graph is such that there are many "draws" in distance, these draws have to be sorted out.
1. If there are several equivalent routes, we store them ALL.
2. For example, you can get all such routes, and optimize gas stations on each.
You can also store a list of "distance, number of gas stations" with a lexicographic order on it and another operation "add + refuel" instead of a distance.
OPTION 2. The number of gas stations is a priority over the distance.
Similar to the first one, only the role of the distance is played by the pair “number of gas stations, distance” with the lexicographic order on it.