# Algorithms questions

package edu.princeton.cs.algorithms; import edu.princeton.cs.introcs.StdIn; import edu.princeton.cs.introcs.StdOut; /************************************************************************* * Compilation: javac Arbitrage.java * Execution: java Arbitrage < input.txt * Dependencies: EdgeWeightedDigraph.java DirectedEdge.java * BellmanFordSP.java * Data file: http://algs4.cs.princeton.edu/44sp/rates.txt * * Arbitrage detection.

* * % more rates.txt * 5 * USD 1 0.741 0.657 1.061 1.005 * EUR 1.349 1 0.888 1.433 1.366 * GBP 1.521 1.126 1 1.614 1.538 * CHF 0.942 0.698 0.619 1 0.953 * CAD 0.995 0.732 0.650 1.049 1 * * % java Arbitrage < rates.txt * 1000.00000 USD = 741.00000 EUR * 741.00000 EUR = 1012.20600 CAD * 1012.20600 CAD = 1007.14497 USD * *************************************************************************/ /** * The Arbitrage class 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.

*

* For additional documentation, * see Section 4.4 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

* * @author Robert Sedgewick * @author Kevin Wayne */ public class Arbitrage { // this class cannot be instantiated private Arbitrage() { } /** * 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) { // V currencies int V = StdIn.readInt(); String[] name = new String[V]; // create complete network EdgeWeightedDigraph G = new EdgeWeightedDigraph(V); for (int v = 0; v < V; v++) { name[v] = StdIn.readString(); for (int w = 0; w < V; w++) { double rate = StdIn.readDouble(); DirectedEdge e = new DirectedEdge(v, w, -Math.log(rate)); G.addEdge(e); } } // find negative cycle BellmanFordSP spt = new BellmanFordSP(G, 0); if (spt.hasNegativeCycle()) { double stake = 1000.0; for (DirectedEdge e : spt.negativeCycle()) { StdOut.printf("1:"+"%10.5f %s ", stake, name[e.from()]); stake *= Math.exp(-e.weight()); StdOut.printf("2:"+"= %10.5f %s\n", stake, name[e.to()]); } } else { StdOut.println("No arbitrage opportunity"); } } }