$(20$ pts$.)$ Shortest Path in Currency Trading. Shortest path algorithms can be applied in currency trading.

Let $c_1,c_2,$dots,$c_n$ be various currencies; for instance, $c_1$ might be dollars, $c_2$ pounds, and $c_3$ lire. For any two

currencies $c_i$ and $c_j,$ there is an exchange rate $r_{i,j}$; this means that you can purchase $r_{i,j}$ units of currency

$c_j$ in exchange for one unit of $c_i.$ These exchange rates satisfy the condition that so that if you

start with a unit of currency $c_i,$ change it into currency $c_j$ and then convert back to currency $c_i,$ you end up

with less than one unit of currency $c_i($the difference is the cost of the transaction$).$

$($a$)$ Give an efficient algorithm for the following problem: Given a set of exchange rates $r_{i,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 weights are real numbers.

$($b$)$ The exchange rates are updated frequently, reflecting the demand and supply of the various curren$-$

cies. Occasionally the exchange rates satisfy the following property: there is a sequence of currencies

$c_{i_1},c_{i_2},$dots,$c_{i_k}$ such that $r_{i_1,i_2}*r_{i_2,i_3}dots{r}_{i_{k-1},i_k}*r_{i_k,i_1}>1.$ This means that by starting with a unit of currency

$c_{i_1}$ and then successively converting it to currencies $c_{i_2},c_{i_3},$dots,$c_{i_k},$ and finally back to $c_{i_1},$ you would

end up with more than one unit of currency $c_{i_1}.$ Such anomalies last only a fraction of a minute on the

currency exchange, but they provide an opportunity for risk$-$free profits. Give an efficient algorithm

for detecting the presence of such an anomaly. Use the graph representation you found above.