Altorithm Currency Exchange (Android / Java / Pseudocode)

Question

I have a problem finding a good solution to the currency problem. I have been thinking about this all day with any elegant and quick solution for all occasions.

Statement:

We have exchange rates, such as ...

• EUR to USD → 1.37
• USD to AUD → 0.7
• MEX to CAD → 1.8
• LIB to YEN → 2.3
• (.....)

These rates are not real and may change once a day. The number of bets can be as large as the currencies in the world (about 150).

We are invited to convert the amount of money from any currency to another, and we must give an answer (if possible) taking into account exchange rates.

The best case is that you exchange directly (displayed in the list), in the worst case you have to jump several times at intermediate exchange rates.

Note: taking into account EUR to USD, you can assume that uSD in EUR is the opposite.

I hope the problem is clear.

Any ideas?

Answer 1

Build a weighted oriented graph with each vertex labeled with a currency name. If you have a rate for AB currency, add an edge (A, B) with the exchange rate as weight.

If you have an edge (A, B) but not an edge (B, A), add an edge (B, A) with a weight of 1 divided by weight (A, B).

To convert the currency C to D, use the shortest path algorithm to find the lowest weight path from peak C to peak D. If there is no such path, then conversion is not possible. See a directed graph with non-negative weights .

==================================================== =======================================

It will not necessarily find the best exchange rate because the rates are multiplying. This can be done to find the best speed using the logarithms of exchange rates as edge weights and using the shortest path algorithm that can handle negative edge weights.

To find the exchange path with the least number of exchanges, give each edge that corresponds to a direct exchange weighing 1.

Answer 2

I would mostly agree with Patricia. But this problem, of course, is certainly related to avoiding arbitration. Thus, it boils down to the “shortest path” (minimum cost) from currency A to currency B. The shortest route algorithms are well studied and documented. Look at them in the feed and outfit.