5 ms·
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,
by bhl 3y ago
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.
Edit: the algorithm you’re describing exists btw https://en.m.wikipedia.org/wiki/Johnson%27s_algorithm https://en.m.wikipedia.org/wiki/Johnson%27s_algorithm
- schneems 3y agoI 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.
- bhl 3y ago> 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.
- schneems 3y agoTo 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?
- bhl 3y agoYes, 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.
- heavenlyblue 3y ago> 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)
- klyrs 3y agoI use regenerative braking as a driving application -- you gain energy by going downhill. A negative cycle would look like an Escher drawing.
- empath-nirvana 3y agoIf 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).
- bhl 3y agoYep! Executing arbitrage is definitely harder than finding they exist though.