A negative cycle is a directed cycle where the sum of the edge weights is negative.
A shortest paths tree exists if and only if there are no negative cycles. This is kind of obvious: If a negative cycle exists, one can keep going around the cycle getting lower and lower weights without bound, so there can’t be a SPT.
Bellman-Ford Algorithm
The algorithm is the following:
Initialize \(d(s)=0\) and \(d(v)=\infty\) for all other nodes. Let there be \(N\) nodes. Relax all the edges. Then repeat. Repeat \(N\) times.
You may not need to iterate \(N\) times. You may terminate early if in any iteration all relaxations leave the distances unchanged.
If your digraph has no negative cycles, the SPT is calculated in time \(O(N\times M)\) In practice, it is often much faster due to early termination.
Another improvement is noting that if a given node’s distance did not change in one iteration, you do not need to relax edges pointing from it in the next iteration.
Note that this algorithm improves upon Dijkstra’s in that it can work if you have negative weights, as long as there are no negative cycles.
Detecting Negative Cycles
If in the last iteration of the algorithm, some node’s distance changes, then a negative cycle exists, and includes that node. edgeTo will give you that cycle if you follow it.
Question: Proof?
In practice, you’d search for a negative cycle earlier (how?)
Applications of Negative Cycles
Arbitrage on currencies. If you can make money by converting a chain of currencies all the way back to the currency you began with, you’ve found a negative cycle (same principle applies with stocks, etc).
The graph of currencies is complete: Each edge is the exchange rate. If the product of the numbers in the cycle exceeds 1, you can make money. Just replace the weights with their logarithms and the problem is transformed to sums.