public class Arbitrage extends Object
Arbitrageclass provides a client that finds an arbitrage opportunity in a currency exchange table by constructing a complete-digraph representation of the exchange table and then finding a negative cycle in the digraph.
This implementation uses the Bellman-Ford algorithm to find a negative cycle in the complete digraph. The running time is proportional to V3 in the worst case, where V is the number of currencies.
This code is guaranteed to find an arbitrage opportunity in a currency exchange table (or report that no such arbitrage opportunity exists) under the assumption that all arithmetic performed is without floating-point rounding error or arithmetic overflow. Since the code computes the logarithms of the edge weights, floating-point rounding error will be present and it may fail on some pathological inputs.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
|Modifier and Type||Method and Description|
Reads the currency exchange table from standard input and prints an arbitrage opportunity to standard output (if one exists).
public static void main(String args)
args- the command-line arguments