Graph Theory37 sections · 1633 units
Open in Course

Application: Currency Arbitrage

(Detecting profit cycles)

You have exchange rates between currencies. Can you start with one currency, make a series of exchanges, and end with more than you started?

This is arbitrage. Model currencies as nodes and exchange rates as edge weights. Convert rates to logarithms: weight=−log⁡(rate)weight = -\log(rate). A profitable cycle becomes a negative cycle because log⁡(r1⋅r2⋅r3)=log⁡(r1)+log⁡(r2)+log⁡(r3)\log(r_1 \cdot r_2 \cdot r_3) = \log(r_1) + \log(r_2) + \log(r_3).

Run Bellman-Ford to detect the negative cycle. If found, you can profit by following the cycle. The logarithm trick converts multiplication to addition, making the problem fit Bellman-Ford.