I have a graph, each edge is some positive weight. To search for the shortest route between two points, I use the Dijkstra's algorithm. I have an additional condition: the system of gas stations. I.e. some vertices are "refills" that make up our reserve, and no refills I can only move a certain n (n is the sum passed from the filling of the edge weights). How, then, should I minimize the number of gas stations on the route? If we are within node with dressing, we don't necessarily have to use it.

asked April 3rd 20 at 18:32

3 answers

answered on April 3rd 20 at 18:34

First look for all possible ways with fillings: ([current dressing:at what distance runs] + [current stock of fuel: what is the max distance you can drive without refueling] - [the sum of edges of the path from the current node to the next gas station or destination] ) > 0.

Select all the possible options, that was always fuel in the tank.

Then, only one of them, looking for the minimum number of gas stations on the fast track.

Select all the possible options, that was always fuel in the tank.

Then, only one of them, looking for the minimum number of gas stations on the fast track.

answered on April 3rd 20 at 18:36

Subject to these constraints it is possible to create an artificial graph, where each vertex corresponds to a vertex in the original graph and some fuel (I will denote such a vertex (v, f) is the vertex v with f the fuel).

Vertices in this graph will be up to 500*10000. For each edge v->u l in the original graph, create an edge from vertex (v, f) to a vertex (u, f-l) for all f (i.e., from vertex v having f fuel, you can get to vertex u, with f-l fuel). These edges price 0. Also, each vertex v where there is a gas station, add the edge (v, f) -> (v, n) price 1 (filled up position). In the graph will be to 500*10000 + 500*10000 ribs.

Now run there is a BFS and two queues, or a deque of vertices (start, n) until you find a path to any vertex (finish, f). The path length is equal to the number of gas stations. The transient at the edges of price 1 is the filling process, the ribs prices 0 - just movement in the original graph.

It is a known generalization of BFS on the graph 0-1:

When you take the top of the deque and see all of its neighbors, if the length of the rib to the neighbor is 1, then put the end rib to the end of the deque, and if the price is 0 in the beginning. With two queues is done as follows: while queue is not empty, take the top from the current queue and put its neighbors at distance 0 to the end of the same queue, and neighbors through an edge of length 1 - second. When the current queue is empty, move on to another and so on.

Vertices in this graph will be up to 500*10000. For each edge v->u l in the original graph, create an edge from vertex (v, f) to a vertex (u, f-l) for all f (i.e., from vertex v having f fuel, you can get to vertex u, with f-l fuel). These edges price 0. Also, each vertex v where there is a gas station, add the edge (v, f) -> (v, n) price 1 (filled up position). In the graph will be to 500*10000 + 500*10000 ribs.

Now run there is a BFS and two queues, or a deque of vertices (start, n) until you find a path to any vertex (finish, f). The path length is equal to the number of gas stations. The transient at the edges of price 1 is the filling process, the ribs prices 0 - just movement in the original graph.

It is a known generalization of BFS on the graph 0-1:

When you take the top of the deque and see all of its neighbors, if the length of the rib to the neighbor is 1, then put the end rib to the end of the deque, and if the price is 0 in the beginning. With two queues is done as follows: while queue is not empty, take the top from the current queue and put its neighbors at distance 0 to the end of the same queue, and neighbors through an edge of length 1 - second. When the current queue is empty, move on to another and so on.

answered on April 3rd 20 at 18:38

OPTION 1. Distance priority the number of gas stations.

My decision in each vertex to store not just a figure of distance traveled, and the list is: "distance/fuel up/top". And distance, and fuel does not decrease.

With these lists you can do the following operations:

1. Add distance + spent fuel. For each element of the list distance' = distance + x fuel' = fuel โ y. If it turns out the lack of fuel โ well, not lucky, this element in the list will not.

2. Add distance + to spend fuel + gas. Similarly, but leaving one element corresponding to the smallest distance, where a lack of fuel. distance' = distance + x fuel' = full tank.

3. Add another item to the list. Then remove from the list those items where the distance is not less, and the amount of fuel not more.

Thereafter, the optimal route, optimize refills.

If the graph is such that there are many "draws" in distance, these have a tie to resolve.

1. If there are several equal routes stored them ALL.

2. For example, you can get all those routes and at each to optimize the pump.

You can also instead of the distance to keep a list of "distance, the number of gas stations" the lexicographic order on her and with another operation: "add+to refuel".

OPTION 2. The number of gas stations a priority range.

Similar to the first, only the role of distance plays a pair of "number of gas stations, the distance" lexicographic order on it.

My decision in each vertex to store not just a figure of distance traveled, and the list is: "distance/fuel up/top". And distance, and fuel does not decrease.

With these lists you can do the following operations:

1. Add distance + spent fuel. For each element of the list distance' = distance + x fuel' = fuel โ y. If it turns out the lack of fuel โ well, not lucky, this element in the list will not.

2. Add distance + to spend fuel + gas. Similarly, but leaving one element corresponding to the smallest distance, where a lack of fuel. distance' = distance + x fuel' = full tank.

3. Add another item to the list. Then remove from the list those items where the distance is not less, and the amount of fuel not more.

Thereafter, the optimal route, optimize refills.

If the graph is such that there are many "draws" in distance, these have a tie to resolve.

1. If there are several equal routes stored them ALL.

2. For example, you can get all those routes and at each to optimize the pump.

You can also instead of the distance to keep a list of "distance, the number of gas stations" the lexicographic order on her and with another operation: "add+to refuel".

OPTION 2. The number of gas stations a priority range.

Similar to the first, only the role of distance plays a pair of "number of gas stations, the distance" lexicographic order on it.

Find more questions by tags Algorithms

@Cora.Langworth, Logic build - consider all possible options. Here you can go and be in the top 42 with 1 "liters" of fuel. And can like something else to go and come back with 100 liters of fuel. Here is 2 different vertices in the new graph. They are all different from 0 to n. You have all the state is described by two numbers: where you are and how much you have fuel now fuel. We are all the state space is described with the help of this artificial graph. After all, absolutely no matter what you used, because if you are in the top 42 with 10 liters of fuel, you can continue to do the same. So it turns out n * "number of vertices" of the vertices in the new graph. Next, we in the state space looking for the minimum path. - eusebio.Price16 commented on April 3rd 20 at 18:48