title: Interesting Problem (Currency arbitrage)
body: <p>Arbitrage is the process of using discrepancies in currency exchange values to earn profit.<br>
  Consider a person who starts with some amount of currency X, goes through a series of exchanges and finally ends up with more amount of X(than he initially had).<br>
  Given n currencies and a table (nxn) of exchange rates, devise an algorithm that a person should use to avail maximum profit assuming that he doesn't perform one exchange more than once.</p>
  
  <p>I have thought of a solution like this:  </p>
  
  <ol>
  <li>Use modified Dijkstra's algorithm to find single source longest product path.</li>
  <li>This gives longest product path from source currency to each other currency.  </li>
  <li>Now, iterate over each other currency and multiply to the maximum product so far, <code>w(curr,source)</code>(weight of edge to source).  </li>
  <li>Select the maximum of all such paths.</li>
  </ol>
  
  <p>While this appears good, i still doubt of correctness of this algorithm and the completeness of the problem.(i.e Is the problem NP-Complete?) as it somewhat resembles the traveling salesman problem.  </p>
  
  <p>Looking for your comments and better solutions(if any) for this problem.</p>
  
  <p>Thanks.</p>
  
  <p><b>EDIT:</b><br>
  Google search for this topic took me to this <a href="http://courses.csail.mit.edu/6.046/spring04/handouts/ps7sol.pdf" rel="noreferrer">here</a>, where arbitrage detection has been addressed but the exchanges for maximum arbitrage is not.This may serve a reference.</p>