A prototypical example today is to take battery range into account in navigation. You charge your battery going downhill, corresponding to a negative edge weight. If you're driving from the top of a mountain, through a valley, to the top of a hill, many of the available routes might end up with a negative cost!
Preprocessing is certainly possible, but the result is to densify the graph. That densification can turn a sparse graph with O(n) edges into a dense graph with O(n^2) edges. When the goal is to keep pathfinding to a nearly-linear (roughly O(vertices + edges) with log factors) runtime in the presence of negative weight edges, naive preprocessing blows the budget before you even start pathfinding.
The article at hand presents long-sought after algorithms which hit the near-linear runtime goal at the cost of a combination of clever preprocessing and a novel divide&conquer approach. So yes, preprocessing, no, not "just" preprocessing.
You can preprocess the battery range problem quite efficiently. If is not possible to gain more charge than the gravitational potential between the endpoints for any path. You can change all of the edge weights from battery charge changes into battery charge as compared to a perfectly efficient car.
This would make a downhill edge A->B and uphill edge B->A both have approximately the cost of the average between them which should be decidedly non-negative.
The potential energy from going down hill varies based on vehicle load. A pickup truck filled with gravel or an SUV hauling a trailer would be in a very different situation than the same vehicle making the trip empty the next day.
Driver behavior, wind, heater use, preconditioning the battery, etc mean this stuff really should be computed in real time by the vehicle in question.
Vehicle load will also affect charge loss on flat ground. The entire graph would need to be updated for a different vehicle or load setup.
I was simply stating that it is possible to update a graph with negative edges into one with only positive edges in O(E) preprocessing time for this usecase.
Even that’s a false assumption, the weighs may depend both on the vehicle’s starting position and the path it took.
Suppose you’re starting at 1 mile of altitude and your destination is at sea level. You might gain change over the trip, except if the vehicles battery ever hits full charge you can’t store the excess charge you should be gaining.
Net result you there are multiple paths to finish the trip with higher charge than you started with and the goal is pick the optimal one of those. The most efficient trip could therefore involve minimizing drops in altitude until you’ve freed up enough battery to contain that excess energy.
The problem with capacity limits is harder yet again and I don't think the discussed algorithms help you (except in so far as if their optimal choice doesn't hit the capacity limit, then its the optimal choice).
For any given points A-B the overall change in altitude will be the same no matter which route you take. Extra charging from going down a steep hill will typically _never_ make up for the fact you will need to spend more energy traveling on flat or even uphill to make up for it.
The most optimal route for any vehicle is almost always the shortest one. Failing that, avoiding uphills is typically more important than aiming for downhills and these are not the same thing.
If the option is to gain 10kWh then lose 10kWh or lose 10kWh then gain 10kWh they net to 0 kWh but the order may be critical. If your battery is full then one path costs 10kWh and the other 0kWh. On the other hand if your battery is almost empty then the first past may work where the second requires a visit to a charge station.
A more realistic scenario is less extreme but the same principle can apply. You can’t always calculate optimal paths without knowing available battery power and which segments are negative.
Preprocessing is certainly possible, but the result is to densify the graph. That densification can turn a sparse graph with O(n) edges into a dense graph with O(n^2) edges. When the goal is to keep pathfinding to a nearly-linear (roughly O(vertices + edges) with log factors) runtime in the presence of negative weight edges, naive preprocessing blows the budget before you even start pathfinding.
The article at hand presents long-sought after algorithms which hit the near-linear runtime goal at the cost of a combination of clever preprocessing and a novel divide&conquer approach. So yes, preprocessing, no, not "just" preprocessing.