What’s an application where you’d absolutely have to have a graph with negative weights? Couldn’t you just preprocess the edges and normalize their weights?
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.
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.
Driver behavior, wind, heater use, preconditioning the battery, etc mean this stuff really should be computed in real time by the vehicle in question.
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.
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 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.
Consider, for example, the problem of moving an electric car with regenerative braking along a grid of very hilly roads, using minimal charge from the battery. When you go down a hill, sure, you can add energy to your battery by hitting the brakes. But when you go uphill again, you may have to drain your battery of charge.
Indeed, if you can find a course which is largely downhill, you may very well end uo with a "negative amount of energy charged" to the battery :-)
Compared to Dijkstra's original algorithm of E + V log V, naively pre-processing edges would require V^2 work assuming an edge can exist between each vertex.
Edit: the algorithm you’re describing exists btw https://en.m.wikipedia.org/wiki/Johnson%27s_algorithm
I don’t know any off hand. I would guess its when a path has a benefit incurred rather than a cost. I.e. in a monopoly board it might be shorter to get to a destination by getting thrown in jail first, but the longer path around the whole board comes with a benefit I.e. negative weight of receiving $200 by crossing the start.
Your reply does help clarify the “why not normalize” which is helpful. I’m still curious for other examples of negative weights.
This is a non-contrived example. You could do this as a mini-project where you scrape various foreign exchange or cryptocurrency data, and try to find some arbitrage opportunities by running these shortest path algorithms.
Though with arbitrage, you typically want to find a cycle like BCAB so you have more of the initial currency you started off with.
No it "could" result in an infinite loop. For driving situations negative weights would probably never yield infinite cycles due to negative weight. For that to happen some laws of physics would need to change drastically (i.e. a longer path yielding lower energy usage the longer it gets is nonsensical in any sense that is sensical in the physical world)
In case it’s unclear, the article from OP is effectively doing this:
> The team found it was possible to divide the input graph into clusters of low-diameter subgraphs, and then to progressively rework the weights using a series of price functions to build a restructured graph that could be processed almost completely using Dijkstra's algorithm. This involved the random removal of paths with negative weights that would enable the source graph to be converted into a directed acyclic graph: one with only forward paths and no loops connecting the strongly connected clusters to each other. This form was selected because it opened the door to tools that would allow the use of the fastest algorithm. A later phase then reintroduces the missing negative-weight edges. The small number of these paths can be processed using the Bellman-Ford algorithm with comparatively little impact on runtime.
To me, adding a constant to all edges seems like an obvious idea to try-- but one issue is that it will distort the ranking for paths that have different numbers of edges. Ideally a normalisation would preserve the ranking of paths so that a path with minimal unnormalised weight would also be a path of minimal normalised weight. But ranking won't be preserved by adding a constant C to all edge weights, now paths with more edges will be unfairly penalised.
Yeah, as you explained that is not useful because it does not preserve the shortest-path of the original graph (which is the reason we are making all edges non-negative in the first place).
That is why Johnson's algorithm adds an edge-dependent weight to each of the edges.
At that point you are already spending |V||E| time, so you are not getting anywhere close to the performance of Dijkstra and the new algorithm.
But I guess you are saying that this preprocessing is OK if you need to run many single-source-shortest-path queries on the graph.
How exactly?
Edit: Oops, as another commenter points out above, this penalizes paths with more steps. I knew it was too easy. :P
I think you can prove that one can't just map the edge weights (so that edge's new weight only depends on its original weight) to make all weights positive, and also preserve all shortest paths.
You may try something more complex, i.e. where the new weight of an edge would depend on some more edges around it. But then the cost of doing so may be close to Bellman-Ford algorithm itself.
This obviously has a potentially exponential complexity, though it will work if there isn't too much negativity. It should at least be enough to convince you that preprocessing is possible absent the existence of negative cost loops.