Description
arbitrage
the simultaneous buying and selling of the same negotiables or commodities in different markets in order to make an immediate
profit. (Encarta(R) World English Dictionary (C) 1999)
One market where arbitrage can be applied is in the buying and selling of currencies. Dollars can be exchanged for pounds that can be
exchanged for pesos that can be exchanged for dollars to end up with more dollars than you started with.
The assignment
Your assignment is to:
1. build a directed weighted graph that represents exchange rates. Each node of the graph represents a currency (such as dollars) and
each directed weighted edge represents the exchange rate (the edge weight is what you multiply the from-node by to get the
corresponding amount of currency in the to-node).
2. find sequences of trades that will result in a profit. Print out the trades and the resulting profit if $1000 is invested (or 1000 of the
currency that you start with).
Input Data
The input data should be read in from a file that has the following format:
The first line in the file contains an int representing the number of different currencies.
Each subsequent line represents one exchange with the name of the from-node, the name of the to-node and a real number that
shows the exchange rate.
For example, the file might look like the following:
4
dollar peso .0412
franc pound 1.731
dollar pound 1.0153
peso franc 14.321
peso dollar 24.8804
pound franc .58793
