A car trip where there are gas stations with unlimited gasoline and parts for one time use.The parts permanately increase the size of the gas tank (measured in mileage) but the parts, once used, cannot be used again. The car itself originally has a tank that can travel a certain number of miles. What would be the best way to find out the initial minimum gas tank size needed to traverse between two Gas Stations as well as finding out what gas stations can be initially traversed using a certain gas tank?
I initially tried Dijkstra but it doesn't work on negative values and I don't think a Minimum Spanning Tree is the best because it doesn't necessairly minimize the distance between two nodes. My initial thought would be to find an algorithm that can return the total minimized edge weights (including negatives) of two values but not sure how to do that
CodePudding user response：
A basic algorithm can work as follows.
Keep a collection of unreached stations, with the distance from the currently reachable stations set initially to infinity, except for the initial station, for which the distance is empty.
Pick the station with the lowest distance. If it's above the capacity of the fuel tank, then you're stuck.
If the station is the target station, then you've succeeded.
Otherwise, update the distances of any unvisited stations immediately adjacent to the chosen station with the distances from this new station (if doing so reduces their distance). Update the capacity of the fuel tank with the part in the current station.
Repeat from step 2, "Pick the station..."
This gives you a method to find whether a particular station is reachable given an initial fuel tank size.
It's easy to modify this algorithm to find the minimal initial fuel tank size needed to reach the target station. Start with a fuel tank of size 0, and every time you get stuck (in step 2), increase that initial fuel tank size just enough that you're not stuck.
For the set of unreached stations, you can use a Fibonacci heap as in Dijkstra's algorithm to get O(m n log n) runtime (m = total number of roads, n = total number of gas stations).
CodePudding user response：
The key observation is that if you can get to any n different gas stations, then you can go to all of them, collect all of their gas tank enhancements, and drive around between all reachable stations however much you like.
Since it only matters which stations you can connect to, you don't have to remember anything about the paths required to get there, and you can solve this using a simple variant of an MST algorithm.
As we perform Prim's algorithm, for example, we can keep track of the total size of all reachable gas tank augments.
Perform Prim's algorithm starting at the initial station, until you get to the destination. Whenever you add a new station, subtract the current total augment size from the edge distance to figure out how much initial tank it takes to get there. Then add the station's augment to your total.
Your answer is the maximum initial tank requirement that you discover until you reach the destination.