We are looking for how Belmann ford fits this problem.

Currency arbitrage is a form of financial trading that uses discrepancies in foreign currency exchange rates to transform one unit of some currency into more than one unit of the same currency. For instance, suppose 1 U.S. dollar bought 0.82 Euro, 1 Euro bought 129.7 Japanese Yen, 1 Japanese Yen bought 12 Turkish Lira and one Turkish Lira bought 0.0008 U.S. dollars. Then, by converting currencies, a trader could start with 1 U.S. dollar and buy 0.82 times 129.7 times 12 times 0.0008 TildeTilde 1.02 U.S. dollars, thus turning a 2% profit. Of course, this is not how real currency markets work because each transaction must pay a commission to a middle-man for making the deal. Suppose that we are given n currencies c_1, c_2, ellipsis, C_n and an n times n table R of exchange rates, such that one unit of currency c_i buys R[i, j] units of currency c_j.A traditional arbitrage opportunity is thus a cycle in the induced graph such that the product of the edge weights is greater than unity. That is, a sequence of currencies lang c_i_1, c_i_2, ellipsis c_i_k rang such that R[i_1, i_2] times R[i_2, i_3] times ellipsis times R[i_k - 1, i_k] times R[i_k, i_1] > 1. Each transaction, however, must pay a commission, which is typically some alpha fraction of the transaction value, e.g., alpha = 0.01 for a 1% rate. Give an efficient algorithm to determine whether or not there exists such an arbitrage opportunity, given a commission rate alpha. Analyze the running time of your algorithm. Dumbledore's hint: It is possible to solve this problem in O(n^3). Recall that Bellman-Ford can be used to detect negative-weight cycles in a graph. Explain what effect varying alpha has on the structure of the set of possible arbitrage opportunities your algorithm might identify. Currency arbitrage is a form of financial trading that uses discrepancies in foreign currency exchange rates to transform one unit of some currency into more than one unit of the same currency. For instance, suppose 1 U.S. dollar bought 0.82 Euro, 1 Euro bought 129.7 Japanese Yen, 1 Japanese Yen bought 12 Turkish Lira and one Turkish Lira bought 0.0008 U.S. dollars. Then, by converting currencies, a trader could start with 1 U.S. dollar and buy 0.82 times 129.7 times 12 times 0.0008 TildeTilde 1.02 U.S. dollars, thus turning a 2% profit. Of course, this is not how real currency markets work because each transaction must pay a commission to a middle-man for making the deal. Suppose that we are given n currencies c_1, c_2, ellipsis, C_n and an n times n table R of exchange rates, such that one unit of currency c_i buys R[i, j] units of currency c_j.A traditional arbitrage opportunity is thus a cycle in the induced graph such that the product of the edge weights is greater than unity. That is, a sequence of currencies lang c_i_1, c_i_2, ellipsis c_i_k rang such that R[i_1, i_2] times R[i_2, i_3] times ellipsis times R[i_k - 1, i_k] times R[i_k, i_1] > 1. Each transaction, however, must pay a commission, which is typically some alpha fraction of the transaction value, e.g., alpha = 0.01 for a 1% rate. Give an efficient algorithm to determine whether or not there exists such an arbitrage opportunity, given a commission rate alpha. Analyze the running time of your algorithm. Dumbledore's hint: It is possible to solve this problem in O(n^3). Recall that Bellman-Ford can be used to detect negative-weight cycles in a graph. Explain what effect varying alpha has on the structure of the set of possible arbitrage opportunities your algorithm might identify