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)