USD10.7410.6571.06183.67EUR1.3510.8891.43391.11GBP1.5211.12611.614108.12CHF0.9430.6980.62194.04INR0.0120.0110.00920.0111

Note that diagonal values are equal to one.

We have a graph like this:

check-currency-arbitrage-with-bellman-ford-eg.excalidraw

Solution

Method 1 - The Dijkstra Approach (And Its Flaw)

A straightforward approach is to apply Dijkstra's algorithm to the transformed graph to find the shortest path.

However, this method has a critical flaw: Dijkstra's algorithm fails if the graph has a negative-weight cycle. In currency exchange, such a cycle isn't just a theoretical problem—it represents a real-world arbitrage opportunity. When this condition exists, Dijkstra's cannot find the correct answer.

Method 2 - Bellman-Ford Algorithm

When represented as a graph, the vertices correspond to the currencies, and the edges correspond to the exchange rates. Since our table is complete, the graph is also complete. The key insight is to transform the multiplicative nature of exchange rates into an additive one by taking the logarithm of the rates and negating them. Then, to solve this problem, we need to find a cycle whose edge weights product is greater than 1.

This transformation turns the problem of finding an arbitrage opportunity into detecting a negative-weight cycle in the graph.

Lemma Any amount of currency u can be obtained from currency S if and only if u is reachable from some node w where dist[w] decreased during the V-th iteration of Bellman-Ford.

We have already seen:

We know that:

Related Tags