Shortest path algorithms can be applied in currency trading. Let  c1,  c2, … , cn be vario...

Shortest path algorithms can be applied in currency trading. Let  c1,  c2, … , cn be various currencies; for instance, c1 might be dollars, c2 pounds, and c3 lire. For any two currencies ci and cj, there is an exchange rate ri,j ; this means that you can purchase ri,junits of currency cj in exchange for one unit of ci. These exchange rates satisfy the condition that ri ,j . rj,i<1, so that if you start with a unit of currency ci, change it into currency cj and then convert back to currency ci, you end up with less than one unit of currency ci (the difference is the cost of the transaction).

(a) Give an efficient algorithm for the following problem: Given a set of exchange rates ri,j , and two currencies s and t, find the most advantageous sequence of currency exchanges for converting currency s into currency t. Toward this goal, you should represent the currencies and rates by a graph whose edge lengths are real numbers.

The exchange rates are updated frequently, reflecting the demand and supply of the various currencies. Occasionally the exchange rates satisfy the following property: there is a sequence of currencies   such that  This means that by starting with a unit of currency  and then successively converting it to currencies   and finally back to   , you would end up with more than one unit of currency . Such anomalies last only a fraction of a minute on the currency exchange, but they provide an opportunity for risk-free profits.

(b) Give an efficient algorithm for detecting the presence of such an anomaly. Use the graph representation you found above.