Currency Exchange Altorithm (Android / Java /Pseudocode)

Question

I have a problem finding a good solution to the exchange currency problem. I've spent all the day thinking about this with any elegant and fast solution for all cases.

Statement:

We have some exchange currency rates like...

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

This rates are not real and could change once a day. The number of rates could be as big as currencies are in the world (around 150).

We are asked to convert an amount of money from any currency to another one and we should give the answer (if we can) given the exchange currency rates.

The best case is if you exchange is direct (appears on the list), in the worse case you should jump a LOT of times in intermediate exchanges rates.

Note: Given EUR to USD you can assume uSD to EUR is the inverse.

I hope the problem is clear.

Any ideas??

Answer 1

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

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

To convert currency C to D, apply a shortest path algorithm to find the lowest weight path from C's vertex to D's vertex. If there is no such path, the conversion cannot be done. See directed graph with non-negative weights.

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

This won't necessarily find the best exchange rate, because the rates multiply. It could be made to find the best rate by using logarithms of exchange rates as edge weights, and using a shortest path algorithm that can handle negative edge weights.

To find the exchange path with the fewest exchanges, give each edge that matches a direct exchange a weight 1.