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
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.