3 ms·
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
by schneems 3y ago
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.
- 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.