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?
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.
Its pretty hard to give any problem which you absolutely have to solve using only one particular technique. Nevertheless, there are some problems which require more than just being able to add positive numbers together in order to solve.
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 :-)
The issue with negative weighted edges is that a cycle would result in an infinite loop when finding shortest path, compared to when all edges are non-negative, cycles can be safely skipped.
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.
I think the question isn’t “what is the issue with negative weights” rather “what is a real world example of negative weights” which the article doesn’t really explain.
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.
> In finance, for example, there may be situations in currency or options trading where buying and selling in one sequence is more profitable than taking a different path, and these can be modeled using negative weights as long as the search algorithm is fast enough.
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.
To try to restate that. Someone owns currency A then buys B which is a cost, but it has a good exchange rate with currency C and C has a good exchange rate with A. So the B-C-A move yields a profit which would be representative as a negative weight. Is that right?
Yes, if trading BCA results in a profit, either BC or CA has negative weight. Negative weight here just means you can sell a currency more than its cost basis, and or buy a currency for cheaper than its cost basis.
Though with arbitrage, you typically want to find a cycle like BCAB so you have more of the initial currency you started off with.
If I understand correctly, if you find such a loop in a graph of currency exchange rates, that would represent an arbitrage opportunity where you can basically make "infinite money" (although typically those loops close quickly if they're exploitable in the real world).
> The issue with negative weighted edges is that a cycle would result in an infinite loop when finding shortest path
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)
The problem lies in the non-monotonous structure of the sequence of weight when combining positive and negative weights, which is incompatible with Dijkstra's greedy search, which requires monotonous weight sequences in the traversal.
>In finance, for example, there may be situations in currency or options trading where buying and selling in one sequence is more profitable than taking a different path, and these can be modeled using negative weights as long as the search algorithm is fast enough. But those negative weights can throw Dijkstra's shortest-path algorithm for a loop.
The obvious model of that to me would involve all positive weights representing the exchange ratio, but a path through a graph like that wouldn't be summing the edge weights. I guess the idea is that you weight the edges with the log of the exchange ratio?
> Couldn’t you just preprocess the edges and normalize their weights?
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.
A sibling comment linking to Johnson's algorithm shows a way to do it.
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.
> To me, adding a constant to all edges seems like an obvious idea to try
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.
I'm an uber eats driver picking up a long delivery but notifications comes in for grubhub and Doordash for two short deliveries with pickups and dropoffs along my existing route.
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.
Assuming a directed graph. At the entry to each negative edge collect all the nodes reachable in 1 extra hop from that edge and compute the total cost. All that have a positive weight, add as edges from the source of the negative edge. If they still have a negative weight, expand further. Once you're done, drop all the negative edges. This essentially replaces every negative edge with a set of 'shortcuts' that encode all the places the negative edge could have gotten you, such that the shortcuts have positive cost. Use regular Dijkstra on the augmented graph.
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.
> Bellman-Ford instead needs many more steps: The total is based on the product of the number of nodes and vertices.
> reduced the complexity to the square root of the number of vertices multiplied by the number of nodes
At first I thought it was a synonym for vertices, in the same way the article inconsistently uses "connections" for edges. But then "nodes" gets used in the same breath as "vertices" in a way that contradicts that hypothesis.
Looks like a significant and confusing typographical error to me. In the 2nd and 3rd item I think by "nodes" they actually meant "edges". The paper in question in the 3rd item you listed is Scaling algorithms for the shortest paths problem, in which the paper says [1] the complexity is proportional to the square root of the number of "nodes", multiplied by the number of "arcs" (edges).
I only had a quick skim but the first paper describes a graph transformation to remove cycles. So I think that nodes are essentially a subgraph of vertices that contain cycles.
This is precisely the sort of article where a bit of notation and interactive graphics would go far in presenting the information. Anyone who can understand this article knows big-O notation. It's silly to assume the article is more accessible just because it's in English.
